【每日一题】tokitsukaze and Soldier

题意

每个士兵都有一个战力值和人数要求条件，选他组队就有满足他的条件，求队伍最大战力。

solution

一看就是老优先队列了。先按人数要求把每个士兵排个序，然后依次放入队列，因为每个士兵容纳人数是从大到小的，因此我们就只需要考虑是否满足当前士兵容纳人数就好了。优先队列按战力从小到大排序，保证每次删除的士兵战力是最小的，这样就可以满足整体最优，整个过程中维护最大值为答案即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,now,res;
struct Node
{
    ll v,s;
    friend bool operator <(Node a,Node b)
    {
         return a.v>b.v;
    }
}p[200005];

bool cmp(Node a,Node b)
{
    return a.s>b.s;
}

priority_queue<Node>q;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i].v>>p[i].s;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        q.push(p[i]);
        now+=p[i].v;
        while(!q.empty()&&q.size()>p[i].s)
        {
            now-=q.top().v;
            q.pop();
        }
        res=max(res,now);
    }
    cout<<res<<'\n';
    return 0;
}