【每日一题】tokitsukaze and Soldier

tokitsukaze and Soldier

https://ac.nowcoder.com/acm/problem/50439

题目

题目描述：
在一个游戏中，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)。

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

解析

首先亮出我们这道题的知识点：贪心+优先队列（堆）。

但是看到这道题的两个因素，我不禁陷入了迷惑：

这道题想到用贪心是挺简单的，但是贪谁呢？

贪心讲解：

带着这个想法，我们最开始有两种想法，一是贪战斗力，二是贪队伍编制。
不过聪明的你们肯定知道都是不可能的。所以不管我们贪啥，我们要把所有情况的最大值选出来。
在这里我按照队伍编制进行排序（因为编制和集体有关，而战斗力只和个人有关），由此来求出每个编制下的最大战力。
你可能会觉得，为啥求个最大战力，还要排个序呢？别急，这不是为了方便下面的计算呢吗~

打代码咯：

首先我们保存下每个士兵的战力和编制期望。然后按照上面所说的，按编制顺序给排个序。
然后根据我们所说的：要求出每个编制下的最大战力，说明我们在超出编制的情况下，删除元素一定要删除最小的元素。
删除最小元素，我们当然的想到了优先队列。但是看到第一、二点，我们突然发现，每种情况的最大值之间其实是有关系的！（不好意思我没发现）
其实你可能还是不能理解为啥要排个序，但是看到下面的操作你就懂了。

比如我们在某一编制值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);
}

最后把最大值输出就好啦！（详情看代码和例子）

举例：

加入我们一开始有三个士兵{v = 100, s = 1} {v = 5, s = 3} {v = 2, s = 2}。
这三个士兵，我们按照排序的话就是{v = 5, s = 3} {v = 2, s = 2} {v = 100, s = 1}。
我们依次来算3,2,1编制下的最大值：先将{5,3}士兵入队，编制满足3以内，不用删人。（这里就是3的最大编制，不包含后面的是因为，如果包含的话会缩小编制，导致就不是3的编制了）
然后将{2,2}士兵入队，编制满足2以内，不用删人（我们在这里不用考虑前面的编制了，因为拍过序，前面一定是大的编制），同理这里是2的最大编制。
最后将{100,1}士兵入队时，超出了编制1，所以我们要将战斗力最小的人删除，直到编制为1。
所以我们最后依次删除了{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;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏