题解 | #tokitsukaze and Soldier#

考察知识点：贪心、优先队列

读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列顶端的士兵战力（即最低战力）从 cnt 中减去，直到优先队列大小不超过当前士兵的 s[i] 值为止（由于已经进行了降序排序，所以当前的 s[i] 一定是已选择士兵中最低的 s 值），每次更新答案 ans 为 max(ans, cnt)。

时间复杂度：

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vpii vec(n);
    for (int i = 0; i < n; i++)
    {
        int v, s;
        cin >> v >> s;
        vec[i] = {s, v};
    }
    sort(vec.begin(), vec.end(), greater<pii>());
    priority_queue<int, vi, greater<int>> pq;  // 小根堆
    ll cnt = 0, ans = 0;
    for (int i = 0; i < n; i++)
    {
        int v = vec[i].second, s = vec[i].first;
        cnt += v;
        pq.push(v);
        while (pq.size() > s)
        {
            cnt -= pq.top();
            pq.pop();
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}