tokitsukaze and Soldier（3月25日题目 贪心、优先队列、堆）

tokitsukaze and Soldier

题目链接
题解链接

思路：
贪心策略。
考虑按照人数由大到小排序，然后从左往右依次让士兵加入队伍，那么最后一个加入队伍的就是队伍人数的标准s[i]，如果超过了这个人数，我们从队伍中依次踢除战力最小的，那这样我们就可以用一个优先队列存储在队伍中的战力值。时间复杂度$O(n \log n)$O(nlogn)。

Code：

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
struct node
{
    ll v;
    int s;
    bool operator<(const node &A) const { return s > A.s; }
} a[maxn];
priority_queue<ll, vector<ll>, greater<ll> > q;
int main()
{
    int n;
    scanf("%d", &n);
    rep(i, 1, n) scanf("%lld%d", &a[i].v, &a[i].s);
    sort(a + 1, a + n + 1);
    ll temp = 0, ans = 0;   //temp记录当前队伍中的总战力
    rep(i, 1, n)            //枚举所有可选择的人数
    {
        temp += a[i].v;
        q.push(a[i].v);           //把当前这个士兵加入队列中，以s[i]作为队伍人数标准
        while (q.size() > a[i].s)
        {
            temp -= q.top();
            q.pop(); //人数超标了就删除战力最小的一个
        }
        ans = max(ans, temp);
    }
    printf("%lld\n", ans);
    return 0;
}