← 返回题目列表

Codeforces · 1615/A

A. 缩小差距

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

一排有 $$$n$$$ 块塔,其中塔 $$$i$$$ 的高度为 $$$a_i$$$。您是建筑团队的一员,您希望使建筑物看起来尽可能漂亮。在一天之内,您可以执行以下操作:

- 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$),并将一个方块从塔 $$$i$$$ 移到塔 $$$j$$$。这实际上使 $$$a_i$$$ 减少了 $$$1$$$,并增加了 $$$a_j$$$ $$$1$$$。

你认为建筑物的丑陋在于最高和最矮建筑物之间的高度差。正式地,丑陋被定义为$$$\max(a)-\min(a)$$$。

在任意天数之后,您能达到的最低限度的丑陋程度是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 建筑物的数量。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$) — 建筑物的高度。

输出

对于每个测试用例,输出一个整数 - 建筑物的最小可能的丑陋程度。

示例

输入 #1

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

输出 #1

0
0
1

注意

在第一个测试用例中,丑陋程度已经是$$$0$$$。

在第二个测试用例中,您应该执行一个操作,其中 $$$i = 1$$$ 和 $$$j = 3$$$。新的高度现在为 $$$[2, 2, 2, 2]$$$,丑陋度为 $$$0$$$。

在第三个测试用例中,您可以执行三个操作:

1. $$$i = 3$$$ 且 $$$j = 1$$$。新数组现在将为 $$$[2, 2, 2, 1, 5]$$$,
2. $$$i = 5$$$ 且 $$$j = 4$$$。新数组现在将为 $$$[2, 2, 2, 2, 4]$$$,
3. $$$i = 5$$$ 且 $$$j = 3$$$。新数组现在将为 $$$[2, 2, 3, 2, 3]$$$。