考察知识点:贪心、优先队列
读入每个士兵的信息,按照士兵的 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;
}