这个东西怎么做啊阿嗄

Question

Monocarp正在玩电脑游戏，它杀了n个怪物，每一个怪物都有对应的健康度。

Monocarp的角色有两个咒语，他可以任意多次（可能是零）释放：

精确选择两个活着的怪物，并将其生命值降低1
选择一个怪物并杀死它。
当怪物的生命值为0时，它就会死亡。

为了杀死所有怪物，Monocarp应该执行的最低施法次数是多少？

输入
第一行包含一个整数t（1≤t≤10^4）—测试用例的数量。

每个测试用例的第一行包含一个整数n(1≤n≤100) —怪物的数量。

第二行包含n个整数，h1,h2,,,（1≤hi≤100） —每个怪物的健康。

输出
对于每个测试用例，打印一个整数——为了杀死所有怪物，Monocap应该执行的最小法术施放次数。

输入数据 1
3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5

输出数据 1
3
3
5

Answer 1

参考GPT和自己的思路：题目描述：

给定n个怪物，每个怪物有一个初始健康值。有两种魔法，第一种可以选择两个健康值大于0的怪物，将它们的健康值各减少1；第二种可以选择一个健康值大于0的怪物，将它的健康值变为0。问至少需要多少次魔法才能将所有怪物的健康值变为0？

思路：

我们可以发现，第一种魔法的实际效果就是消耗了两个怪物的健康值之和。因此我们可以想到这样一个贪心策略：每次选择两个健康值最大的怪物进行第一种魔法操作。

如果我们只能使用第一种魔法，那么实际上我们最后要达到的目标就是使所有怪物的健康值相等，并且最后的健康值都为0。因此我们可以将原问题转化为：将n个数都减少为最小值所需的操作次数。

如何用第二种魔法呢？可以想到第二种魔法可以抵消最后一次第一种魔法的效果。因此我们只需要在最后所有怪物健康值都相等时使用一次第二种魔法即可。

代码：