题目描述

在一个游戏中，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

分析

本文使用的方法为堆的思路，首先按照限制人数s对结构数组a从大到小进行排序，然后开始循环遍历，首先将当前遍历到的数组a[i]的战力v压入栈中，并且将tmp加上当前v值，之后对s数值进行判断，与当前q队列的大小进行比较，如果是队列内容大于s的值，那么需要将tmp的值减掉小根堆的根节点，也就是去掉最小值，直到当前队列大小不在大于s的值，然后比较当前tmp和ans值得大小，获得结果。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100020;
#define LL long long 
priority_queue<LL , vector<LL> , greater<LL> > q;
struct ty
{
    int v;
    int s;
}a[maxn];
bool cmp(struct ty p1, struct ty p2)
{
    return p1.s > p2.s;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld %d",&a[i].v,&a[i].s);
    }
    sort(a,a+n,cmp);
    LL ans = 0,tmp = 0;
    for(int i=0;i<n;i++)
    {

        q.push(a[i].v);
        tmp += a[i].v;
        while(q.size()>a[i].s)
        {
            tmp -= q.top();
            q.pop();
        }
        ans = max(ans , tmp);
    }
    printf("%lld\n",ans);
    return 0;
}