按照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; }