题意
在一个游戏中,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); }