问题 4775 --最少操作几次

4775: 最少操作几次★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 282  解决: 180
[提交][状态][命题人:]

题目描述

给定一个整数数组a[1n]。现在,希望执行一定数量的操作(可能为零),使数组的所有元素变得相同(即,成为a1=a2==an)

在一次操作中,可以选中若干元素,并将选中的元素每个数加1

例如,设a=[4,2,1,6,2]

可以执行以下操作:选择第1个、第2个和第4个,并将这些元素增加1

这次操作后可以得到的数组为a=[5,3,1,7,2]。

使数组的所有元素彼此相等(即变为a1=a2=.....)所需的最小操作数是多少

输入

输入的第一行包含一个整数t(1T10^4)测试中的测试用例数。

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

每个测试用例描述的第一行包含一个整数n(1N50-数组a中的元素数量

每个测试用例描述的第二行包含n个整数a1a2,…,an1ai10^9-数组a的每个元素

输出

对于每个测试用例,打印一个整数使数组的所有元素都相等的最小操作数

样例输入
Copy
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
样例输出
Copy
3
4
1

提示

第一个测试用例:

a=[3,4,2,4,1,2]

a3a5,对它们执行一个加一的运算,结果得到a=[3,4,3,4,2,2]

再取a1a5a6,对它们加上1进行运算,结果得到a=[4,4,3,4,3,3]

再取a3a5a6,对它们加上一个运算,结果得到a=[4,4,4,4,4,4]

第二个测试用例:

a=[10001002998]

我们取a1a3两次,对它们执行一个加一的运算,结果得到a=[100210021000]

同样,再取a3 两次,在其上执行一个加一的操作,结果得到a=[10021002, 1002]

第三个测试用例:

a=[12,11]

a2,对其执行一个加一的运算,结果得到a=[12,12]

来源

[提交][状态]