塔子哥喜欢肝模拟宇宙,而且特别喜欢用黑塔单通(坐牢)模拟宇宙
有一天,他遇到了n个怪物,第i个怪物的生命值为hi。 由于被守护者之影禁用了普通攻击,黑塔现在只能使用E技能攻击敌人。具体地说,黑塔每次使用E技能,会对敌方全体造成E点伤害。 除此之外,每当一个怪物的生命值首次减小到其最大生命值的50%及以下(含50%)时,如果敌方尚有怪物存活(生命值大于零),那么黑塔就会自动释放一次追加攻击“转圈圈”,对敌方全体造成R点伤害。如果一次攻击同时使多个敌人满足以上条件,那么黑塔也会连续释放多次“转圈圈”,直到“转圈圈”次数耗尽或者敌人全部倒下为止。在“转圈圈”结束之前,黑塔无法再次使用E技能。 作为天才俱乐部#83的天才,黑塔只用了0.0114514秒就算出了自己需要使用多少次E技能才能击败这些怪物,以及在这个过程中她会释放多少次“转圈圈”。她觉得这个问题太简单了,于是将其留给了你作为课后习题。
这题需要考虑的细节有点多。
假设数组nums,首先需要证明的是,对于排序后的数组,元素nums[i](不考虑最后一个元素)如何在更小的AOE释放次数下删除。如果nums[i]能够被k次E技能删除,那么nums[i-1]一定也可以,相应的之前的一定都可以。由于题目指定了R一定大于0,那么如果释放更多次R范围伤害,也能减少E技能的使用。
所以贪心的思路如下:
(1)首先将数组进行排序,从前往后遍历数组,将尽可能靠前的较小元素削减到50%及一下(这种削弱对后面的更大元素也同时造成),用两个变量cntE和cntR统计两个技能的使用次数。
(2)这里暂时不需要考虑中途把某个元素爆成0的情况,从样例也可以看出,就算中途哪个元素被抬走了,它也会贡献一个R技能