每日一题 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;
}