看到牛客的每日一题挺有意思，决定刷一刷看看。
本来想从后往前的，一看发现有点难，还是从头开始吧，应该前面简单点吧。
先做第一期的第一题tokitsukaze and Soldier（3月25日）

题目是这样的，从N个士兵中挑选一些组成一个团，每个士兵有一个战力v[i]和一个要求s[i]，这里的s[i]表示第i个士兵要求团里最多只有s[i]个人他才参加。问最高战力是多少？
士兵人数n<=10^5

题目类型：
贪心、堆（优先队列）

思路：
一开始是想着能不能排个序贪心看看，结果发现不行。
让我们分析一下，假设参加的人数为k,那么我们只需要从满足s[i]>=k的人中挑选战力最高的k个人就可以了。
这个性质我们很容易想到用堆解决。
我们可以对k从大到小进行枚举，对于当前枚举的k，我们可以知道s[i]==k的人，由于k是从大到小枚举的，因此s[i]>k的我们已经放到堆里了。那么我们只要把这部分人放到堆中，然后从大到小取出k个求和就可以了。
这里由于堆的性质，我们需要频繁进行pop和push，这样会导致超时。
所以我们稍微改进一下，我们始终维护堆中最大的k个元素，当有新加入的元素时先加入，然后我们从堆中删除最小的元素直到剩下k个元素，过程中我们可以计算和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[100005],cnt;
int n;
ll maxians;
struct node{
    int v,s;
}p[100005],q[100005];

bool cmp1(node a,node b){
    if(a.s==b.s)return a.v>b.v;
       return a.s<b.s;
}
struct cmp2{
    bool operator()(node a,node b){
        return a.v>b.v;
    }
};

priority_queue<node,vector<node>,cmp2>qu;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].v>>p[i].s;
    sort(p+1,p+1+n,cmp1);
   // for(int i=1;i<=n;i++)cout<<p[i].v<<' '<<p[i].s<<endl;
    for(int i=1;i<=n;i++){
        if(p[i].s!=p[i-1].s)d[++cnt]=p[i].s;
    }
    int la;
    ll tot=0;
    for(int i=n;i>=1;i--){
        if(d[cnt]==p[i].s)qu.push(p[i]),tot+=p[i].v;
        else {
            la=i;
            break;
        }
    }
    for(int k=cnt-1;k>=1;k--){
        int people=d[k];
        while(people<qu.size()){
            node now=qu.top();
            tot-=now.v;
            qu.pop();
        };
        for(int i=la;i>=1;i--){
            if(p[i].s==people){
                node now=qu.top();
                if(p[i].v>now.v){
                    qu.pop();
                    tot-=now.v;
                    tot+=p[i].v;
                    qu.push(p[i]);
                }
            }
            else {
                la=i;
                break;
            }
        }

        maxians=max(maxians,tot);
    }
    cout<<maxians<<endl;
    //*/
    return 0;
}