这个东西怎么做啊是的

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和自己的思路：这是一个贪心算法的问题。首先，如果有两个怪物生命值相等，最优的选择是将它们两个都杀掉，因为这样可以省去一次操作。如果有三个怪物生命值相等，最优的选择是将其中两个杀掉，然后再将剩余的两个杀掉，因为先杀掉其中一个再杀掉两个显然不是最优的选择。所以我们可以先将怪物按生命值从小到大排序，然后每次选择两个生命值最小的怪物进行操作，直到只剩下一个或没有怪物可以操作。这样的算法时间复杂度为$O(n\log n)$。