每日一题 3月25日 tokitsukaze and Soldier 优先队列
程序员文章站
2022-03-06 08:02:02
...
题目链接:https://ac.nowcoder.com/acm/problem/50439
思路:思路:我们考虑按s[i]存入vectoc,从大到小枚举s[i]的值。那么就是在所有>=s[i]的士兵中选v最大的s[i]个。我们可以优先队列维护。因为s[i]是减小的。所以删除的士兵一定在后面用不到。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
priority_queue<LL, vector<LL>, greater<LL> > q;
vector<LL> ve[100005];
int main(){
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
LL v, s;
scanf("%lld%lld", &v, &s);
ve[s].push_back(v);
}
LL ans=0, sum=0;
for(int i=n; i>=1; i--){
for(auto u: ve[i]){
sum+=u;
q.push(u);
}
while(q.size()>i){
sum-=q.top();
q.pop();
}
ans=max(ans, sum);
}
printf("%lld\n", ans);
return 0;
}