题目
题目描述:在一个游戏中,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; } //函数区