按照s从大到小排序。先选s大、宽容的人,他能接受的人最多,然后再不断选s小的人。如果人数超了,就把战斗力最低的人踢掉(贪心完的后悔)。这样其实是决定枚举最大人数的人,先找s大的人,就不会对后面有影响,不会出现:我的s满足了,但上一个选进来的人s不满足。这样保证后面来的人能容忍的人少,前面人的s大,不影响结果。
保证人数的确定,由后来的人决定和影响,这样每个人才能有决定队伍人数的机会。
这样也是在从大到小枚举队伍中的人数,每次看看符合s的人有多少,再从中挑v大的人
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > q;//小根堆
struct person{
ll v;
int s;
}a[100010];
int n;
int comp(struct person x,struct person y){//按照容忍度s从大到小排序
return x.s>y.s;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n;
for(int i=0;i<n;i++)
cin >> a[i].v >> a[i].s;
sort(a,a+n,comp);
ll ans=0;//当前战斗力
ll maxans=0;//最大战斗力
int num=0;//目前选了的人数
for(int i=0;i<n;i++){//按照s从大到小依次选人
num++;
q.push(a[i].v);
ans+=a[i].v;
while(num>a[i].s){
//此时队伍人数不能多于a[i].s
ll x=q.top();//找到战斗力最小的人
q.pop();
num--;
ans-=x;
}
maxans=max(ans,maxans);
}
cout << maxans << "\n";
return 0;
}

京公网安备 11010502036488号