牛客网【每日一题】3月25

题号：NC50439
名称： tokitsukaze and Soldier
来源：练习赛50-C
链接标题 链接:https://ac.nowcoder.com/acm/problem/50439

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述

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

第一行包含一个正整数n(1≤n≤10^5)。
接下来n行，每行包括2个正整数v,s(1≤v≤10^9,1≤s≤n)。

输出描述:

输出一个正整数，表示团的最大战力。

示例1
输入

2
1 2
2 2

输出

3

示例2
输入

3
1 3
2 3
100 1

输出

100

思路
所求的最大战斗力由v和s这两个因素限制。
结构体数组a存放v和s，然后对其排序，先按照s从大到小，如果s相同再排v，也是从大到小（先要保证足够的人数，后面好进行取舍）。
定义一个从小到大的优先队列q，ans相互跟随q，（q每次添加一个战力值，同时用ans加上战力值；ans删去，q也弹出），战力值的先后加入由s的排序决定，当q的元素数量大于当前s的值时（s是由大到小的排序的），就将多出的部分pop出（q是从小到大排序，所以弹出的总是其中最小值），再用ans减去，这样ans的值即为在人数限定在s内的最佳情况（因为弹出的是最小值，相对于前s个数的和，所以之后也不用再考虑被弹出的数），记录ans的最大值
我刚开始提交是70多分，想了一阵子才发现是数组开小了（笑哭）

#include<map>
#include<queue>
#include<bits/stdc++.h>
#define maxn 100004
using namespace std;
struct node{
    long long int v,s;    
};
node a[maxn];
bool cmp(node a,node b)
{
    if(a.s!=b.s)return a.s>b.s;
    else return a.v>a.v;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].v>>a[i].s;
    }
    sort (a+1,a+1+n,cmp);
//    int tot=0;
    long long int ans=0;
    int minn=maxn;
    long long int maxx=0;
    priority_queue<int,vector<int>,greater<int> >q;
    for(int i=1;i<=n;i++)
    {
        q.push(a[i].v);
        ans+=a[i].v;
        while(q.size()>a[i].s)
        {

            ans-=q.top();
//            printf("q.size=%d,a[i].s=%d,ans=%d\n",q.size(),a[i].s,ans);
            q.pop();
//            tot--;
        }
        if(ans>maxx)maxx=ans;
    }

    cout<<maxx;
    return 0;
}