【每日一题】tokitsukaze and Soldier

题意：
有n个士兵，每个士兵 i 有武力值v[i]和限制人数s[i]，即：若选择了第 i 个士兵则选择的总人数不能超过s[i]。求v[i]总和的最大值。

思路：
贪心，优先队列。按s[i]从大到小的顺序进行排序并遍历，对于每项v[i]直接入队。若size<=s[i]直接更新ans；若size>s[i]则最小项出队后更新ans。
此方案确保将v[i]足够大的留在队列中，同时也考虑到了v[i]大而s[i]小的情况。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;
const int inf=2e9+9;
const int maxn=1e5+9;
const int maxx=2e5+9;

int n;
P ar[maxn];

bool cmp(P a,P b)
{
    return a.second>b.second;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&ar[i].first,&ar[i].second);
    sort(ar,ar+n,cmp);
    priority_queue<int,vector<int>,greater<int> > que;
    ll ans=0,tmp=0;
    for(int i=0;i<n;i++)
    {
        que.push(ar[i].first),tmp+=ar[i].first;
        while(que.size()>ar[i].second)
            tmp-=que.top(),que.pop();
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans);
}