【每日一题】tokitsukaze and Soldier

戳我传送
题意：
在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。

前备知识：
手写小根堆的实现：

int heap[N],sz=0;
void push(int x){
    int i=sz++;
    while(i>0){
        int p=(i-1)/2;
        if(heap[p]<=x)    break;
        heap[i]=heap[p];
        i=p;
    }
    heap[i]=x;
}
int pop(){
    int ret=heap[0];
    int x=heap[sz--];
    int i=0;while(i*2+1<sz){
        int a=i*2+1,b=i*2+2;
        if(b<sz&&heap[b]<heap[a])    a=b;
        if(heap[a]>=x)    break;
        heap[i]=heap[a];
        i=a;
    }
    heap[i]=x;
    return ret;
}

思路：
贪心+优先队列。
如果贪武力值，按照武力值大小排序，但是每个士兵对人数的加以了限制，每次加人和删掉人都会导致队伍能容纳的人数的变化，而且因为s的值不同，变化完全可能忽上忽下，更重要的是当人数超过限制时我们不知道是删掉限制了人数的士兵还是把多出来的士兵全部删掉。
但是如果贪队伍长度：
1.按队伍长度从大到小排序。
2.从1遍历到n，当a[k+1]进入队列后超出了限制，表明队伍最大的长度是k。
3.如果长度为k的团只有一种，虽然长度为k-1的团大于k种，但是我们不需要那么多种，我们只是要知道第长度为k-1的团的最大值，只要在从长度为k减为k-1（假设有k-1）或者长度还是k-1，队列里有k个士兵，然后加了一个士兵a[k+1]进队，把队列里贡献最小的2个士兵去掉就，当长度变为k-2时，队列里有k-1个士兵，他们的武力值之和就是长度为k-1的最大值了，更小的长度也是一样计算。
4.如果长度为k的团不只一种，那也是就和3中求k-1的长度是一样的，第一次遇到限制k时，武力值之和最大就是前k个士兵武力值之和，第二次遇到限制k时，往队列里加入a[i]，然后删掉贡献最小的士兵。
5.我们就会发现每个长度的最大值只有一个只有一个，而且也好维护，所以可以贪心队伍长度。

Code：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
struct node{
    ll v;
    int s;
    bool operator<(const node&a)const {
        return s>a.s;
    }
}a[100007];
int n;
priority_queue< ll, vector<ll>, greater<ll> >q;
int main() {
    read(n);
    for(int i=1;i<=n;++i) read(a[i].v),read(a[i].s);
    sort(a+1,a+1+n);
    ll ans=0,temp=0;
    for(int i=1;i<=n;++i) {
        temp+=a[i].v;
        q.push(a[i].v);
        while(q.size()>a[i].s) {
            temp-=q.top();
            q.pop();
        }
        ans=max(ans,temp);
    }
    printf("%lld\n",ans);
    return 0;
}