← 返回题目列表

Codeforces · 1624/A

A. 子集加一

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

Polycarp 得到了一个整数数组 $$$a[1 \dots n]$$$ 作为礼物。现在他想要执行一定次数的操作(可能为零),使数组的所有元素变得相同(即变成$$$a_1=a_2=\dots=a_n$$$)。

- 在一次操作中,他可以获取数组中的一些索引,并将这些索引处的数组元素增加 $$$1$$$。

例如,令 $$$a=[4,2,1,6,2]$$$。他可以执行以下操作:选择索引 1、2 和 4,并将这些索引中的数组元素增加 $$$1$$$。结果,一次操作,他就可以得到数组$$$a=[5,3,1,7,2]$$$的一个新状态。

最少需要多少次操作才能使数组的所有元素变得彼此相等(即变成 $$$a_1=a_2=\dots=a_n$$$)?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

以下是输入测试用例的描述。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 数组 $$$a$$$。

每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,打印一个整数 - 使数组 $$$a$$$ 的所有元素相等的最少操作数。

示例

输入 #1

3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11

输出 #1

3
4
1

注意

第一个测试用例:

- $$$a=[3,4,2,4,1,2]$$$ 对 $$$a_3, a_5$$$ 进行加一运算,得到 $$$a=[3,4,3,4,2,2]$$$。
- $$$a=[3,4,3,4,2,2]$$$ 我们对 $$$a_1, a_5, a_6$$$ 进行运算加一,结果我们得到 $$$a=[4,4,3,4,3,3]$$$。
- $$$a=[4,4,3,4,3,3]$$$ 我们对 $$$a_3, a_5, a_6$$$ 进行运算加一,结果我们得到 $$$a=[4,4,4,4,4,4]$$$。

还有其他 $$$3$$$ 操作序列,在应用这些操作之后,所有元素都变得相等。

第二个测试用例:

- $$$a=[1000,1002,998]$$$ 两次,我们对 $$$a_1, a_3$$$ 执行加一操作,结果我们得到 $$$a=[1002,1002,1000]$$$。
- $$$a=[1002,1002,1000]$$$同样对$$$a_3$$$进行2次加一运算,得到$$$a=[1002,1002,1002]$$$。

第三个测试用例:

- $$$a=[12,11]$$$ 对 $$$a_2$$$ 进行加一运算,得到 $$$a=[12,12]$$$。