题目

题目描述:
在一个游戏中,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. 不过聪明的你们肯定知道都是不可能的。所以不管我们贪啥,我们要把所有情况的最大值选出来
  3. 在这里我按照队伍编制进行排序(因为编制和集体有关,而战斗力只和个人有关),由此来求出每个编制下的最大战力
  4. 你可能会觉得,为啥求个最大战力,还要排个序呢?别急,这不是为了方便下面的计算呢吗~

打代码咯:
  1. 首先我们保存下每个士兵的战力和编制期望。然后按照上面所说的,按编制顺序给排个序。
  2. 然后根据我们所说的:要求出每个编制下的最大战力,说明我们在超出编制的情况下,删除元素一定要删除最小的元素
  3. 删除最小元素,我们当然的想到了优先队列。但是看到第一、二点,我们突然发现,每种情况的最大值之间其实是有关系的!(不好意思我没发现)
  4. 其实你可能还是不能理解为啥要排个序,但是看到下面的操作你就懂了。
  5. 比如我们在某一编制值x的情况下,如果要求比当前编制x小一级的编制时:我们只需要把当前编制y的入队,再将编制多出来的人删掉就好啦。
    for (int i = 0; i < n; i++) {
        sum += soldier[i].v;
        que.push(soldier[i].v);
            //将当前轮到的士兵入队
        while (que.size() > soldier[i].s) {
            sum -= que.top(); que.pop();
        }
            //将多出来的士兵(区间要求小),弹出战斗力最小的士兵(增加平均战斗力)
            //由于我们是按士兵兼容性从大到小排序,所以不用担心删多了的情况
        ans = max(ans, sum);
    }
  6. 最后把最大值输出就好啦!(详情看代码和例子)

举例:
  1. 加入我们一开始有三个士兵{v = 100, s = 1} {v = 5, s = 3} {v = 2, s = 2}
  2. 这三个士兵,我们按照排序的话就是{v = 5, s = 3} {v = 2, s = 2} {v = 100, s = 1}。
  3. 我们依次来算3,2,1编制下的最大值:先将{5,3}士兵入队,编制满足3以内,不用删人。(这里就是3的最大编制,不包含后面的是因为,如果包含的话会缩小编制,导致就不是3的编制了)
  4. 然后将{2,2}士兵入队,编制满足2以内,不用删人(我们在这里不用考虑前面的编制了,因为拍过序,前面一定是大的编制),同理这里是2的最大编制
  5. 最后将{100,1}士兵入队时,超出了编制1,所以我们要将战斗力最小的人删除,直到编制为1。
  6. 所以我们最后依次删除了{2,2}{5,3}(我们在这里用了优先队列,所以是这个顺序),最后留下的一个编制为1的最大编制


AC代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
//代码预处理区

const int MAX = 1e5 + 7;
struct Node {
    ll v, s;//个人战斗力,个人期望队伍编制
    bool operator < (const Node& b) const {
        return s > b.s;
    }
} soldier[MAX];
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
//函数预定义区

int main() {
    int n; read(n);//士兵人数
    for (int i = 0; i < n; i++) {
        read(soldier[i].v); read(soldier[i].s); 
    }
    sort(soldier, soldier + n);//按编制排序,便于我们求出各编制最大值
    ll ans = 0, sum = 0;
    priority_queue< int, vector<int>, greater<int> > que;
        //优先队列用于保存个体战斗力
    for (int i = 0; i < n; i++) {
        sum += soldier[i].v;
        que.push(soldier[i].v);
                //将当前轮到的士兵入队
        while (que.size() > soldier[i].s) {
            sum -= que.top(); que.pop();
        }
                //将多出来的士兵(区间要求小),弹出战斗力最小的士兵(增加平均战斗力)
               //由于我们是按士兵兼容性从大到小排序,所以不用担心删多了的情况         ans = max(ans, sum);
    }
    printf("%lld", ans);
    return 0;
}
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;
}
//函数区