tokitsukaze and Soldier
来源:牛客网
题目描述
在一个游戏中,tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。)
tokitsukaze想知道,团的战力最大为多少。
输入描述:
第一行包含一个正整数n(1≤n≤10^5)。
接下来n行,每行包括2个正整数v,s(1≤v≤10^9,1≤s≤n)。
输出描述:
输出一个正整数,表示团的最大战力。
示例1
输入
2
1 2
2 2
输出
3
示例2
输入
3
1 3
2 3
100 1
输出
100
思路:根据题意可知,选的团的人数取决于团中s[i]的最小值,
所以,选择团的时候,可以将选择的团的武力值,可以将选择的人数从大到小排序,
如果已知选择的人数为k,则选择是s[i] 最大的k个人,枚举排好序的序列,然后每次把前k大的维护起来,
利用小根堆,如果堆中元素大于k,则把堆中的元素弹出,最后维护一个团的值
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
struct node{
ll v,s;
}a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i].v >> a[i].s;
sort(a,a+n,[](const node &x,const node &y){
return x.s > y.s;
});
priority_queue<ll,vector<ll>,greater<ll>> heap;
ll sum = 0,ans = 0;
for(int i = 0; i < n; i ++){
sum += a[i].v;
heap.push(a[i].v);
while(heap.size() && heap.size() > a[i].s) sum-= heap.top(),heap.pop();
ans = max(ans,sum);
}
cout << ans << "\n";
return 0;
}