每日一题 3.25 tokitsukaze and Soldier

这是一个贪心题
按容纳人数排序 当新加入的人的容纳人数小于总人时 去除人数差个战力最小的人
每次加入人都会记录一下最大值
最后就求出了军团战力的最大值

#include <bits/stdc++.h>
#define ll long long
ll const N=1e5+5;
using namespace std;
ll n,v[N],s[N];
priority_queue<ll, vector<ll>, greater<ll> > q;
struct T{
int v,s;
}k[N];
bool cmp(T a,T b){
    return a.s>b.s;
};
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;++i)scanf("%d%d",&k[i].v,&k[i].s);
   sort(k+1,k+1+n,cmp);
   ll z=0,ans=0;
   for(int i=1;i<=n;++i)
   {
      z+=k[i].v;
      q.push(k[i].v);
      while(q.size()>k[i].s)
      {
          z-=q.top();
          q.pop();
      }
      ans=max(ans,z);
   }
    cout<<ans<<endl;
    return 0;
}