题目描述

米小游喜欢肝模拟宇宙，而且特别喜欢用黑塔单通（坐牢）模拟宇宙

有一天，他遇到了$n$个怪物，第$i$个怪物的生命值为$h_i$。 由于被守护者之影禁用了普通攻击，黑塔现在只能使用E技能攻击敌人。具体地说，黑塔每次使用E技能，会对敌方全体造成E点伤害。 除此之外，每当一个怪物的生命值首次减小到其最大生命值的50%及以下(含50%)时，如果敌方尚有怪物存活(生命值大于零)，那么黑塔就会自动释放一次追加攻击“转圈圈”，对敌方全体造成R点伤害。如果一次攻击同时使多个敌人满足以上条件，那么黑塔也会连续释放多次“转圈圈”，直到“转圈圈”次数耗尽或者敌人全部倒下为止。在“转圈圈”结束之前，黑塔无法再次使用E技能。 作为天才俱乐部#83的天才，黑塔只用了0.0114514秒就算出了自己需要使用多少次E技能才能击败这些怪物，以及在这个过程中她会释放多少次“转圈圈”。她觉得这个问题太简单了，于是将其留给了你作为课后习题。

思路:贪心

$\qquad$这题需要考虑的细节有点多。

$\qquad$假设数组nums,首先需要证明的是，对于排序后的数组，元素nums[i]（不考虑最后一个元素）如何在更小的AOE释放次数下删除。如果nums[i]能够被k次E技能删除，那么nums[i-1]一定也可以，相应的之前的一定都可以。由于题目指定了R一定大于0，那么如果释放更多次R范围伤害，也能减少E技能的使用。

所以贪心的思路如下：

$\quad$（1）首先将数组进行排序，从前往后遍历数组，将尽可能靠前的较小元素削减到50%及一下（这种削弱对后面的更大元素也同时造成），用两个变量cntE和cntR统计两个技能的使用次数。

$\quad$（2）这里暂时不需要考虑中途把某个元素爆成0的情况，从样例也可以看出，就算中途哪个元素被抬走了，它也会贡献一个R技能