← 返回题目列表

Codeforces · 1792/A

A. 游戏力量

中文机器翻译题面 查看原题

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 \cdot 10^4$$$。

输出

对于每个测试用例,打印一个整数 - Monocarp 为了杀死所有怪物而应执行的最少施法次数。

示例

输入 #1

3
4
1 2 1 2
3
2 4 2
5
1 2 3 4 5

输出 #1

3
3
5

注意

在第一个测试用例中,初始运行状况列表为 $$$[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]$$$。