【每日一题】3-24 tokitsukaze and Soldier
题目链接：
题意：
有 n 个士兵，每个士兵有两个值 v[i], s[i]，分别表示第 i 个士兵的战斗力 v[i] 和他的限制人数 s[i]
限制人数的意思是，如果选择这个士兵 k，那么选择的人数不能超过 s[k]
求选择若干个士兵的最大战斗力。
解法：
首先考虑为了使若干个士兵的最大战斗力最大，我们肯定希望人数尽量多，并且他们的战斗力尽量高。
所以我们首先将士兵按照限制人数 s[i] 从大到小排序，为了使人数最多，我们从左往右取士兵，考虑一下边界情况，由于士兵是按照限制人数从大到小排序的，所以可选的人数一定是当前遍历到的士兵的可选人数，然后如果我们接着加入士兵发现超过了可选人数，我们显然希望将战斗力更低的士兵删掉，所以要选择一个数据结构在维护他，我们重新看一下需要，加入一个元素，将战斗力最低的元素拿出来，并删掉，这不就是优先队列嘛，所以在遍历的同时，有优先队列来维护一下选择的士兵就可以了
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define pi pair<int,int>
using namespace std;
pi a[100005];
auto cmp = [](pi q, pi w) {
return q.first > w.first;
};
int main()
{
int n;
sc("%d", &n);
for (int i = 0; i < n; i++)
sc("%d%d", &a[i].first, &a[i].second);
sort(a, a + n, [](pi q, pi w) {
return q.second > w.second;
});
ll ans = 0, sum = 0;
int sz = 0;
priority_queue<pi, vector<pi>, decltype(cmp)>q(cmp);
for (int i = 0; i < n; i++)
{
q.push(pi{ a[i].first,a[i].second });
sz++;
sum += a[i].first;
while (sz > a[i].second)
{
sum -= q.top().first;
q.pop();
sz--;
}
ans = max(ans, sum);
}
printf("%lld\n", ans);
} 
查看20道真题和解析
