← 返回题目列表

Codeforces · 1784/A

A. 怪物(简单版)

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

这是问题的简单版本。在此版本中,您只需找到答案一次。在此版本中,不允许进行黑客攻击。

在电脑游戏中,您正在与 $$$n$$$ 怪物战斗。怪物编号$$$i$$$有$$$a_i$$$生命值,所有$$$a_i$$$都是整数。怪物在生命值至少为 $$$1$$$ 时仍存活。

你可以施展两种类型的法术:

1. 对你选择的任何单个活着的怪物造成 $$$1$$$ 伤害。
2. 对所有活着的怪物造成 $$$1$$$ 伤害。如果此操作导致至少一只怪物死亡(最终获得 $$$0$$$ 生命值),则重复该操作(每次至少有一只怪物死亡时继续重复)。

对怪物造成 $$$1$$$ 伤害,使其生命值降低 $$$1$$$。

类型 1 的法术可以施展任意次数,而类型 2 的法术在游戏中最多可以施展一次。

杀死所有怪物需要施展 1 类法术的最少次数是多少?

输入

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

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 怪物的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 怪物的生命值。

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

输出

对于每个测试用例,打印一个整数 - 杀死所有怪物所需施展类型 1 的法术的最小次数。

示例

输入 #1

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

输出 #1

0
4

注意

在第一个测试用例中,怪物的初始生命值是$$$[3, 1, 2]$$$。施展类型 2 的咒语就足够了:

- 怪物的生命值变为 $$$[2, 0, 1]$$$。由于编号 $$$2$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值变为 $$$[1, 0, 0]$$$。由于编号 $$$3$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值更改为 $$$[0, 0, 0]$$$。由于编号 $$$1$$$ 的怪物死亡,该咒语会重复。
- 怪物的生命值变为 $$$[0, 0, 0]$$$。

由于根本不可能使用类型 1 的法术,答案是 $$$0$$$。

在第二个测试用例中,怪物的初始生命值是$$$[4, 1, 5, 4, 1, 1]$$$。这是最佳的动作序列之一:

- 使用类型 1 的法术,对编号为 $$$1$$$ 的怪物造成 $$$1$$$ 伤害。怪物的生命值变为 $$$[3, 1, 5, 4, 1, 1]$$$。
- 使用类型 1 的法术,对编号为 $$$4$$$ 的怪物造成 $$$1$$$ 伤害。怪物的生命值变为 $$$[3, 1, 5, 3, 1, 1]$$$。
- 使用类型 1 的法术,再次对编号为 $$$4$$$ 的怪物造成 $$$1$$$ 伤害。怪物的生命值变为 $$$[3, 1, 5, 2, 1, 1]$$$。
- 使用类型 2 的法术:怪物的生命值变为 $$$[2, 0, 4, 1, 0, 0]$$$。由于编号为 $$$2$$$、$$$5$$$ 和 $$$6$$$ 的怪物死亡,该咒语会重复。 怪物的生命值变为 $$$[1, 0, 3, 0, 0, 0]$$$。由于编号 $$$4$$$ 的怪物死亡,该咒语会重复。 怪物的生命值变为 $$$[0, 0, 2, 0, 0, 0]$$$。由于编号 $$$1$$$ 的怪物死亡,该咒语会重复。 怪物的生命值变为 $$$[0, 0, 1, 0, 0, 0]$$$。
- 使用类型 1 的法术,对编号为 $$$3$$$ 的怪物造成 $$$1$$$ 伤害。怪物的生命值变为$$$[0, 0, 0, 0, 0, 0]$$$。

类型 1 的法术总共施展 $$$4$$$ 次。可以证明这是最小的可能数。