← 返回题目列表

Codeforces · 1891/C

C. 斯米洛和怪物

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

一个叫 Smilo 的男孩正在玩一个新游戏!游戏中,有 $$$n$$$ 群怪物,第 $$$i$$$ 群包含 $$$a_i$$$ 怪物。游戏的目标是消灭所有怪物。为此,您有两种类型的攻击和一个组合计数器 $$$x$$$,最初设置为 $$$0$$$:

- 第一种:你从$$$1$$$到$$$n$$$中选择一个数字$$$i$$$,使得部落中至少剩下一个数字为$$$i$$$的怪物。然后,你从部落编号 $$$i$$$ 中杀死一只怪物,组合计数器 $$$x$$$ 增加 $$$1$$$。
- 第二种:你从$$$1$$$到$$$n$$$中选择一个数字$$$i$$$,这样部落中至少还剩下$$$x$$$个编号为$$$i$$$的怪物。然后,你使用终极攻击并杀死部落中编号为 $$$i$$$ 的 $$$x$$$ 怪物。之后,$$$x$$$ 重置为零。

你的任务是消灭所有怪物,这意味着任何怪物群中都不应该剩下任何怪物。斯米洛希望尽快获胜,因此他希望以最少的攻击次数赢得比赛。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个输入数据集的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 怪物群的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每个部落中的怪物数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot {10^5}$$$。

输出

对于每个测试用例,输出杀死所有怪物所需的最小攻击次数。

示例

输入 #1

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

输出 #1

4
4
11
5

注意

在第一个测试用例中,我们可以对 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 部落使用第一种类型的攻击,然后使用第二种类型的攻击来消灭 $$$2$$$-nd 部落。我们总共需要 $$$4$$$ 攻击。

在第二个测试用例中,我们可以对$$$1$$$-st和$$$3$$$-rd部落使用第一种类型的攻击,然后使用第二种类型的攻击来消灭$$$2$$$-nd部落,然后对$$$4$$$-th部落使用第一种类型的攻击。我们总共需要 $$$4$$$ 攻击。

在第四个测试用例中,我们可以对$$$1$$$-st部落使用第一种类型的攻击一次,对$$$2$$$-nd部落使用两次,然后对$$$2$$$-nd部落使用第二种类型的攻击,最后使用第一种类型的攻击来消灭$$$2$$$-nd部落。我们总共需要 $$$5$$$ 攻击。