题意

在一个游戏中,tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。)
tokitsukaze想知道,团的战力最大为多少。


思路

考虑到一个解和集合大小只和这个集合里最小的s[i]有关,所以我们把每个士兵按S从大到小排序来枚举这个最小的S[i],那么第i个解就是1~i-1士兵里前s[i]-1大的v之和+v[i]
不断用优先队列维护就行啦


#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod = 998244353;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e6+6;

PII a[maxn];
int n;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].se,&a[i].fi);
    }
    sort(a+1,a+1+n,greater<PII>());

    LL ans=a[1].se,res=a[1].se;
    q.push(a[1].se);
    for(int i=2;i<=n;i++){
        while(q.size()>a[i].fi){
            ans-=q.top();
            q.pop();
        }
        if(q.size()<a[i].fi){
            res=max(res,ans+a[i].se);
        }
        else {
            res=max(res,ans-q.top()+a[i].se);
        }

        q.push(a[i].se);
        ans+=a[i].se;

    }
    printf("%lld\n",res);
}