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

题号：NC50439

名称： tokitsukaze and Soldier

来源：练习赛50-C

戳我进入往期每日一题汇总贴~

题目精讲

---------------------------------------------------------------分析-----------------------------------------------------------------

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

-----------------------------------------------------------以下是解法------------------------------------------------------------

但是想到这里，你应该能发现（也有可能你一开始就发现了），如果我们已知团队人数最多为 ${k}$ ，那么我们的选择是可以贪心的——选 $s_i$ 大于等于 ${k}$ 的武力值最大的 ${k}$ 个人。
那么我们可以考虑枚举这个 ${k}$ （ ${k}$ 的取值并不需要连续，按所有的 $s_i$ 取值就可以），但再枚举 ${k}$ 之后时间复杂度已经不允许再每次都挨个求武力值和了，这时我们来考虑一下这个武力值的和是否可以在枚举 ${k}$ 的过程中就维护出来（你可以考虑从大到小枚举 ${k}$ ，或者从小到大枚举 ${k}$ ，看哪一个可以）。然后我们发现，如果我们从大到小枚举 ${k}$ ， ${k}$ 每减少一次就相当于需要先把 $s_i$ 满条件的人先加进来，然后把多于 ${k}$ 个的武力值最小的几个人删掉，再加入与删除的操作过程中就可以维护所有人的权值和。换句话说，如果我们每次都加入当前还没有进入队伍的 $s_i$ 最大的人，那么只需要在加入他之后删掉超出了这个 $s_i$ 的武力值最小的人就可以了。
而插入与删除的操作需要用一个支持加入元素和删除最小值的数据结构来维护，这个数据结构当然是堆(优先队列)啦！

代码可戳我查看~

---------------------------------------------------以下是介绍堆的分界线---------------------------------------------------------

堆是一种非常有趣的数据结构，他是一棵完全二叉树。有大根堆和小根堆两种（以下我们以小根堆为例介绍它）。它支持插入和删除堆顶（也就是树根）的操作，它也始终满足一个性质——父亲节点的值小于等于其所有子孙，那么显而易见的，整棵树中的根节点的值就是最小的。
那么我们怎么在插入一个数的时候和删除堆顶（根）的时候维持其小根堆的性质呢？
当我们插入一个数的时候，就先将其放在堆的最后一个元素的后面，然后将他与他的父亲进行比较，如果他比他的父亲小，说明不满住小根堆性质，就将其与其父亲交换，交换之后重复这个操作，直到这个数到达它该到的位置。
当我们删除堆顶的时候，可以将最后一个数临时的补到堆顶位置，然后判断他是否可以放在堆顶——即是否是小于其两个儿子，如果不是说明它应该往下交换，将其和两个儿子中的小的那个交换，交换之后继续和他的儿子进行判断和交换，一直到交换到合适的位置。
这样就可以保证一直都是小根堆啦！

在C++的stl里面，有 priority_queue(优先队列) 来实现它，你可以不用自己写直接使用呀！但是请注意priority_queue默认是个大根堆，如果需要变成小根堆的话可以在定义priority_queue时加参数（参见代码），也可也把数取相反数之后放进去。
一点注意事项：队伍的战斗力之和可能会爆int，要使用long long 哦。

一点小建议：没有手写过堆的实现的同学还是应该去自己实现一下。

-----------------------------------------------以下是答疑和回复的分界线---------------------------------------------------

另外在12楼 @Dyswan 同学使用了权值线段树解题，会线段树的同学推荐看一下呀！
先把武力值离散化，所有人按照武力值加入权值线段树；然后按照 $s_i$ 从小到大枚举，每次求当前权值线段树中武力值最大的 $s_i$ 个人的和（区间求和），之后把当前这个人从权值线段树中删掉—— $s_i$ 变大以后这个人不能出现在选择范围里。
多说一句，我们其实也可以最开始让权值线段树空着，然后从大到小枚举 $s_i$ ，每次先把这个人加入权值线段树，然后求武力值最大的 $s_i$ 个人的和（权值线段树中元素个数不到 $s_i$ 的时候是总和）。
其实整体来说，贪心思路还是那样的：枚举团队人数 ${k}$ （或者说是在枚举真正限制了团队人数的那个人），然后 $s_i$ 大 ${k}$ 的武力值最大的 ${k}$ 个。但是你可以用不同的数据结构来维护！所以，千万不要被题解限制了思路哦！

看完邓老师的题解，记得自己去做题提高呀~

欢迎各位大佬来做题写题解，也欢迎大家踊跃在本讨论贴中提问！

活动奖励：