tokitsukaze and Soldier（贪心与优先队列）

在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。
链接：https://ac.nowcoder.com/acm/problem/50439
来源：牛客网

先将士兵按照s从大到小排序，然后按照这个顺序依次选取士兵，这样一来我们就能够选取更多的士兵。

也就是说如果没有后效性，前面的士兵不会影响到后面的士兵的人数要求。

但是选取到后面的时候我们需要将剔除掉部分士兵，选择战力小的士兵依次剔除即可。

所以我们使用一个优先队列来维护选取的士兵。

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
typedef long long ll;
class Solder{
public:
    int v;
    int s;
};

Solder solders[N];

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> solders[i].v >> solders[i].s;
    }
    sort(solders, solders + n, [&](Solder a,Solder b){
        return a.s > b.s;
    });

    priority_queue<int, vector<int> , greater<int>> que;
    ll res = 0, maxv = -0x3f3f3f3f;
    for(auto& s :solders){
        que.push(s.v);
        res += s.v;
        while(que.size() > s.s) {
            res -= que.top();
            que.pop();
        }
        maxv = max(maxv, res);
    }
    cout << maxv << endl;
}

tokitsukaze and Soldier（贪心与优先队列）

原文：https://www.cnblogs.com/waitti/p/13338027.html