【贪心】【堆】tokitsukaze and Soldier

https://ac.nowcoder.com/acm/contest/22904/1004

1. 为什么要排序？

排序是为了先处理人数限制大的士兵。因为人数限制小的士兵会影响后续的选择，优先处理人数限制大的士兵可以让我们选出更多的士兵，最大化战斗力。

• 如果不排序，可能会先处理人数限制小的士兵，导致过早地剔除高战斗力的士兵。
• 排序后，我们可以尽可能多地选士兵，在人数限制大的情况下挑选出战斗力较大的组合，后面再根据限制逐渐减少人数。

2. 为什么要用 max(temp, total_power)？

max(temp, total_power) 是为了更新最大战斗力总和。

• temp 是当前选定士兵的总战斗力，但由于人数限制的原因，某些时刻的总战斗力会减小。
• total_power 保存的是之前计算过的最大战斗力，我们需要不断比较当前战斗力 temp 和之前的最大值 total_power，这样才能确保输出的最终结果是所有可能情况中的最大值。

这一步是为了确保即便在处理人数限制时总战斗力降低，也不会错过之前的最佳组合。

#include <bits/stdc++.h>
using namespace std;

bool compare(pair<int, int>a, pair<int, int> b) {
    return a.first > b.first;
}
int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> soldiers(n);
    for (int i = 0; i < n; i++) {
        int v, s;
        cin >> v >> s;
        soldiers[i] = {s, v}; // s表示人数限制，v表示战力
    }

    // 按照人数限制 s 从大到小排序
    sort(soldiers.begin(), soldiers.end(), compare);

    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆，用于存储已选士兵的战力
    long long total_power = 0; // 团的总战力
    long long temp = 0;
    for (auto [s, v] : soldiers) {
        pq.push(v);          // 将当前士兵的战力加入堆中
        temp += v;    // 增加总战力

        // 如果人数超过了当前士兵的限制，就移除战力最小的士兵
        while(pq.size() > s) {
            temp -= pq.top(); // 移除最小战力
            pq.pop();
        }
        total_power = max(temp, total_power);
    }

    cout << total_power << endl; // 输出最大战力
    return 0;
}