309033: CF1615A. Closing The Gap

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Closing The Gap

题意翻译

有 $n$ 座大楼排成一排,第 $i$ 座大楼的高度为 $a_i$。你是建筑团队的一员,你想让这些大楼看起来尽可能漂亮。 在一天以内你可以选择两个互不相同的大楼 $i,j$,然后使得 $a_i\leftarrow a_i+1$,$a_j\leftarrow a_j-1$。 你认为这些大楼的丑陋程度取决于最高的大楼和最低的大楼之间的高度差。形式化地说,这些大楼的丑陋程度为 $\max\limits_{i=1}^na_i-\min\limits_{i=1}^n a_i$。你想知道若干天之后,这些大楼的丑陋程度的最小值是多少。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 1000$。 - $2\leqslant n\leqslant 100$。 - $1\leqslant a_i\leqslant 10^7$。 Translated by Eason_AC 2021.12.25

题目描述

There are $ n $ block towers in a row, where tower $ i $ has a height of $ a_i $ . You're part of a building crew, and you want to make the buildings look as nice as possible. In a single day, you can perform the following operation: - Choose two indices $ i $ and $ j $ ( $ 1 \leq i, j \leq n $ ; $ i \neq j $ ), and move a block from tower $ i $ to tower $ j $ . This essentially decreases $ a_i $ by $ 1 $ and increases $ a_j $ by $ 1 $ . You think the ugliness of the buildings is the height difference between the tallest and shortest buildings. Formally, the ugliness is defined as $ \max(a)-\min(a) $ . What's the minimum possible ugliness you can achieve, after any number of days?

输入输出格式

输入格式


The first line contains one integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Then $ t $ cases follow. The first line of each test case contains one integer $ n $ ( $ 2 \leq n \leq 100 $ ) — the number of buildings. The second line of each test case contains $ n $ space separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^7 $ ) — the heights of the buildings.

输出格式


For each test case, output a single integer — the minimum possible ugliness of the buildings.

输入输出样例

输入样例 #1

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

输出样例 #1

0
0
1

说明

In the first test case, the ugliness is already $ 0 $ . In the second test case, you should do one operation, with $ i = 1 $ and $ j = 3 $ . The new heights will now be $ [2, 2, 2, 2] $ , with an ugliness of $ 0 $ . In the third test case, you may do three operations: 1. with $ i = 3 $ and $ j = 1 $ . The new array will now be $ [2, 2, 2, 1, 5] $ , 2. with $ i = 5 $ and $ j = 4 $ . The new array will now be $ [2, 2, 2, 2, 4] $ , 3. with $ i = 5 $ and $ j = 3 $ . The new array will now be $ [2, 2, 3, 2, 3] $ . The resulting ugliness is $ 1 $ . It can be proven that this is the minimum possible ugliness for this test.

Input

题意翻译

有 $n$ 座大楼排成一排,第 $i$ 座大楼的高度为 $a_i$。你是建筑团队的一员,你想让这些大楼看起来尽可能漂亮。 在一天以内你可以选择两个互不相同的大楼 $i,j$,然后使得 $a_i\leftarrow a_i+1$,$a_j\leftarrow a_j-1$。 你认为这些大楼的丑陋程度取决于最高的大楼和最低的大楼之间的高度差。形式化地说,这些大楼的丑陋程度为 $\max\limits_{i=1}^na_i-\min\limits_{i=1}^n a_i$。你想知道若干天之后,这些大楼的丑陋程度的最小值是多少。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 1000$。 - $2\leqslant n\leqslant 100$。 - $1\leqslant a_i\leqslant 10^7$。 Translated by Eason_AC 2021.12.25

加入题单

上一题 下一题 算法标签: