Codeforces Round 925 (Div. 3) Problem B（贪心）_there are n containers of water lined up, numbered

B. Make Equal time limit per test ：2 seconds memory limit per test ：256 megabytes input ：standard input output ：standard output

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

You can apply the following operation any (possibly zero) number of times: pour any amount of water from the $i$-th container to the $j$-th container, where $i$ must be less than $j$ (i.e. KaTeX parse error: Expected 'EOF', got '&' at position 2: i&̲lt;j). Any index can be chosen as $i$ or $j$ any number of times.

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

Input

The first line of the input contains a single integer $t$ ($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$ ($1\le n\le 2\cdot 10^5$) — the number of containers with water.

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

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

Output

Output $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.

Example
Input

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
2
3
4
5
6
7
8
9
10
11
12
13

output

YES
NO
YES
NO
NO
YES
1
2
3
4
5
6

此题题目中描述：只能从前面的杯子倒水到后面的杯子，那我们就进行循环，每次循环搜索当前的杯子里的水是不是大于目标值（最终要达到的水量），如果大于目标值，就直接把水倒到下一个杯子里，然后下一个杯子也进行如此操作，一直到最后。

如果期间有任何一个杯子里的水被扫到了是小于目标值的，那么就说明这个数据不可能成功，因为如果都被倒进去水了，还没有达到目标值，就不能再有杯子给他倒水了。

#include<iostream>
using namespace std;

const int N = 2 * 1e5 + 10;

int a[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t; cin >> t;
	
	while (t--) {
		int n; cin >> n;
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum += a[i];
		}

		int tar = sum / n;
		bool flag = 1;

		for (int i = 1; i <= n; i++) {
			if (a[i] > tar) {
				a[i + 1] += (a[i] - tar);
				a[i] = tar;
			}
			else if(a[i] < tar){
				flag = 0;
			}
		}
		
		if (flag)cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39