[每日一题]3.24 tokitsukaze and Soldier

题目网址：https://ac.nowcoder.com/acm/problem/50439

涉及知识点：

• 优先队列/贪心

做法：

• 每个士兵都有战力Vi和一个限制Si，我们先按照每个士兵的Si从大到小进行排序
• 然后我们根据排好序的士兵遍历
• 因为士兵的Si从大到小，所以遍历的过程中，当前遍历的士兵对应的si一定是最小
• 所以我们可以维护一个大小由Si较小的优先队列
• 如果队列大小小于当前遍历士兵的Si，就扔到优先队列里，一旦士兵的人数超过限制，出队，直到队列大小等于当前士兵的Si减一

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
struct node{
    ll v;
    int s;
};
node a[maxn];
bool cmp(node p1,node p2){
    return p1.s > p2.s;
}
priority_queue< ll ,vector<ll>,greater<ll> > q;//小根堆
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld %d",&a[i].v,&a[i].s);
    }
    sort(a+1,a+1+n,cmp);
    ll ans = 0 , cnt = 0;
    for(int i=1;i<=n;i++){
        while(q.size() >= a[i].s){
            cnt -= q.top();
            q.pop();
        }
        q.push(a[i].v);
        cnt += a[i].v;
        ans = max(ans , cnt);
    }
    printf("%lld\n",ans);
    return 0;
}