在一个游戏中,tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。)
tokitsukaze想知道,团的战力最大为多少。
题目
- 原题地址:tokitsukaze and Soldier
- 题目编号:NC50439
- 题目类型:可以后悔的贪心
- 时间限制:C/C++ 1秒,其他语言2秒
- 空间限制:C/C++ 524288K,其他语言1048576K
1.题目大意
- 有
n
个士兵,每个士兵有战力v
以及他们希望被选中后选中的不超过的士兵个数s
,求最后选出的士兵的战力之和的最大值
2.题目分析
- 按容纳人数排序,再用优先队列greater
- 每次加入一个新人,当加入的人的容纳人数小于总人时,去除人数差个战力最小的人
- 每次加入人都会记录一下最大值
3.题目代码
#include<bits/stdc++.h>using namespace std;typedef struct so{int v, s;
}so;bool cmp(so a, so b){if(a.s==b.s)return a.v>b.v;return a.s>b.s;
}int main() {int n;cin >> n;so ss[n];for(int i=0;i<n;i++) cin >> ss[i].v >> ss[i].s;sort(ss,ss+n,cmp);priority_queue<int, vector<int>, greater<int>> q;long long ans = 0, sum = 0;for(int i=0;i<n;i++){sum += ss[i].v;q.push(ss[i].v);while(q.size()>ss[i].s) sum -= q.top(), q.pop();ans = max(sum, ans);}cout << ans << endl;
}