【每日一题】3月25日题目精讲 贪心、优先队列、堆

题目描述

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

题解

如果没有每个士兵的人数限制，显而易见的我们会直接按照武力值大小排序，但是每个士兵对人数的加以了限制，如果我们还是按武力值大小加人的话，每次加人和删掉人都会导致队伍能容纳的人数的变化，而且还是跳跃的变化（完全有可能忽大忽小），更关键的是我们并不知道人数限制不满足了我们该删去谁——是删掉限制了我们人数的那个人扩充容量呢还是按现在的限制把多的人都删掉呢？

但是想到这里，你应该能发现（也有可能你一开始就发现了），如果我们已知团队人数最多为 ，那么我们的选择是可以贪心的——选大于等于 的武力值最大的 个人。那么我们可以考虑枚举这个 ，但再枚举 之后时间复杂度已经不允许再每次都挨个求武力值和了。

这时我们来考虑一下这个武力值的和是否可以在枚举 的过程中就维护出来（你可以考虑从大到小枚举 ，或者从小到大枚举 ，看哪一个可以）。然后我们发现，如果我们从大到小枚举 ， 每减少一次就相当于需要先把 满足条件的人先加进来，然后把多于 个的武力值最小的几个人删掉，再加入与删除的操作过程中就可以维护所有人的权值和。

换句话说，如果我们每次都加入当前还没有进入队伍的最大的人，那么只需要在加入他之后删掉超出了这个的武力值最小的人就可以了。
而插入与删除的操作需要用一个支持加入元素和删除最小值的数据结构来维护，这个数据结构当然是堆(优先队列)啦！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=100010;
struct Node
{
    int v,s;
    bool operator<(const Node &W) const
    {
        return s>W.s;
    }
}a[N];
int n;

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i].v>>a[i].s;
    sort(a,a+n);

    LL sum=0;
    LL ans=0;
    priority_queue<int,vector<int>,greater<int> > heap;
    for(int i=0;i<n;i++)
    {
        sum+=a[i].v;
        heap.push({a[i].v});

        while(heap.size() > a[i].s)
        {
            sum-=heap.top();
            heap.pop();
        }

        ans=max(ans,sum);
    }

    cout<<ans<<endl;

    // system("pause");
}