#CODEFORCESP9243. Make Equal

Make Equal

Make Equal

题面翻译

nn 个装着水的容器,第 ii 个容器中有 aia_i 单位的水。保证 nain \mid \sum a_i

你可以进行若干次操作。每次操作你可以从容器 ii 倒入容器 jj 任意数量的水,但是需要满足 i<ji < j

问最后能否将所有容器中的水量相同。

多测。1t1041 \le t \le 10^4n2×105\sum n \le 2 \times 10^50ai1090 \le a_i \le 10^9

题目描述

There are n n containers of water lined up, numbered from left to right from 1 1 to n n . Each container can hold any amount of water; initially, the i i -th container contains ai a_i units of water. The sum of ai a_i is divisible by n n .

You can apply the following operation any (possibly zero) number of times: pour any amount of water from the i i -th container to the j j -th container, where i i must be less than j j (i.e. i<j i<j ). Any index can be chosen as i i or j j any number of times.

Determine whether it is possible to make the amount of water in all containers the same using this operation.

输入格式

The first line of the input contains a single integer t t ( 1t104 1 \le t \le 10^4 ) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer n n ( 1n2105 1 \le n \le 2 \cdot 10^5 ) — the number of containers with water.

The second line of each test case contains n n integers a1,a2,,an a_1, a_2, \dots, a_n ( 0ai109 0 \le a_i \le 10^9 ) — the amounts of water in the containers. It is guaranteed that the sum of ai a_i in each test case does not exceed 2109 2 \cdot 10^9 . Also, the sum of ai a_i is divisible by n n .

It is guaranteed that the sum of n n over all test cases in the input does not exceed 2105 2 \cdot 10^5 .

输出格式

Output t t lines, each of which is the answer to the corresponding test case. As the answer, output "YES" if it is possible to make the amount of water in all containers the same using the described operation. Otherwise, output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

样例 #1

样例输入 #1

6
1
43
2
1 3
5
4 5 2 1 3
3
1 2 3
7
4 5 5 0 6 4 4
7
6 5 5 1 3 4 4

样例输出 #1

YES
NO
YES
NO
NO
YES

提示

In the third test case of the example ( a=[4,5,2,1,3] a=[4, 5, 2, 1, 3] ), you can proceed as follows:

  • pour 1 1 unit of water from the first vessel to the fourth, then a=[3,5,2,2,3] a=[3, 5, 2, 2, 3] ;
  • pour 1 1 unit of water from the second vessel to the third, then a=[3,4,3,2,3] a=[3, 4, 3, 2, 3] ;
  • pour 1 1 unit of water from the second vessel to the fourth, then a=[3,3,3,3,3] a=[3, 3, 3, 3, 3] .