这是一个贪心题
按容纳人数排序 当新加入的人的容纳人数小于总人时 去除人数差个战力最小的人
每次加入人都会记录一下最大值
最后就求出了军团战力的最大值
#include <bits/stdc++.h>
#define ll long long
ll const N=1e5+5;
using namespace std;
ll n,v[N],s[N];
priority_queue<ll, vector<ll>, greater<ll> > q;
struct T{
int v,s;
}k[N];
bool cmp(T a,T b){
return a.s>b.s;
};
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&k[i].v,&k[i].s);
sort(k+1,k+1+n,cmp);
ll z=0,ans=0;
for(int i=1;i<=n;++i)
{
z+=k[i].v;
q.push(k[i].v);
while(q.size()>k[i].s)
{
z-=q.top();
q.pop();
}
ans=max(ans,z);
}
cout<<ans<<endl;
return 0;
}

京公网安备 11010502036488号