CF1792A GamingForces

Monocarp 正在玩一款电脑游戏。他需要击杀 $n$ 个怪物，第 $i$ 个怪物有 $h_i$ 点生命值。 Monocarp 的角色拥有两种法术，可以任意次数（包括零次）以任意顺序施放： - 选择恰好两个存活的怪物，使它们的生命值各减少 $1$； - 选择一个怪物并直接将其击杀。 当怪物的生命值变为 $0$ 时，该怪物死亡。 请问 Monocarp 至少需要施放多少次法术才能击杀所有怪物？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$），表示怪物的数量。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 100$），表示每个怪物的生命值。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^4$。

对于每个测试用例，输出一个整数，表示 Monocarp 至少需要施放多少次法术才能击杀所有怪物。

在第一个测试用例中，初始生命值列表为 $[1, 2, 1, 2]$。共施放了三次法术： - 第一次法术作用于怪物 $1$ 和 $2$——怪物 $1$ 死亡，怪物 $2$ 生命值变为 $1$，新的生命值列表为 $[0, 1, 1, 2]$； - 第二次法术作用于怪物 $3$ 和 $4$——怪物 $3$ 死亡，怪物 $4$ 生命值变为 $1$，新的生命值列表为 $[0, 1, 0, 1]$； - 第三次法术作用于怪物 $2$ 和 $4$——怪物 $2$ 和 $4$ 都死亡。 在第二个测试用例中，初始生命值列表为 $[2, 4, 2]$。共施放了三次法术： - 第一次法术作用于怪物 $1$ 和 $3$——两只怪物生命值都变为 $1$，新的生命值列表为 $[1, 4, 1]$； - 第二次法术直接击杀怪物 $2$——怪物 $2$ 死亡，新的生命值列表为 $[1, 0, 1]$； - 第三次法术作用于怪物 $1$ 和 $3$——怪物 $1$ 和 $3$ 都死亡。 在第三个测试用例中，初始生命值列表为 $[1, 2, 3, 4, 5]$。共施放了五次法术。第 $i$ 次法术用第二种法术击杀第 $i$ 个怪物。生命值变化序列为：$[1, 2, 3, 4, 5] \rightarrow [0, 2, 3, 4, 5] \rightarrow [0, 0, 3, 4, 5] \rightarrow [0, 0, 0, 4, 5] \rightarrow [0, 0, 0, 0, 5] \rightarrow [0, 0, 0, 0, 0]$。 由 ChatGPT 4.1 翻译