牛客-tokitsukaze and Soldier（贪心+stl优先队列）

原题链接：更好的阅读体验
每日一题题单链接：传送门
题目描述
在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。
输入描述:
第一行包含一个正整数n(1≤n≤10^5)。
接下来n行，每行包括2个正整数v,s(1≤v≤10^9,1≤s≤n)。
输出描述:
输出一个正整数，表示团的最大战力。
示例1
输入
复制
2
1 2
2 2
输出
复制
3
示例2
输入
复制
3
1 3
2 3
100 1
输出
复制
100

思路：
因为s[i]的限制就表明了我们在选的过程中如果在某一步中个数超出s[i]的话就要去掉，贪心一下肯定是去掉v[i]值小的。
如果每一次都sort的话复杂度可能不大乐观，所以就可以用优先队列~
队列的详解用法：传送门
队列与优先队列的总结：传送门
代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
struct node{
    ll v,s;
}a[maxn];
bool cmp(node a,node b){
    return a.s>b.s;
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].v,&a[i].s);
    sort(a+1,a+1+n,cmp);
    priority_queue <int,vector<int>,greater<int> >q;
    ll res=0,sum=0;
    for(int i=1;i<=n;i++){
        q.push(a[i].v);
        sum+=a[i].v;
        while(q.size()>a[i].s){
            sum-=q.top();
            q.pop();
        }
        res=max(res,sum);
    }
    printf("%lld
",res);
    return 0;
}

友好的每日一题开端~