欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每日一题 3月25日 tokitsukaze and Soldier 优先队列

程序员文章站 2022-03-06 08:02:02
...

题目链接:https://ac.nowcoder.com/acm/problem/50439
每日一题 3月25日 tokitsukaze and Soldier 优先队列
思路:思路:我们考虑按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;
}

相关标签: 优先队列