题目描述
塔子哥正在玩一个游戏,游戏中n个怪物,血量上限分别为hi,初始时所有怪物的血量都等于它们的血量上限,当怪物的血量小于或等于0时,怪物将会死亡。
塔子哥有两个技能
第一个技能为旋风斩,消耗一点法力,对所有怪物造成1点伤害
题目思路
考虑暴力枚举,第一个技能如果释放,肯定应该先于第二个技能,这样效果至少不差甚至更优
可以排序后枚举每一个怪物的血量,使用第一个技能让当前怪物血量死亡(其前面的怪物也肯定死亡,血量都比这个怪物少),后面的怪物都使用第二个技能,最终得出的最小花费就是答案。
时间复杂度O(nlogn)
代码