【Codeforces 1462 D】Add to Neighbour and Remove，n方枚举，贪心检查

problem

D. Add to Neighbour and Remove
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Polycarp was given an array of a[1…n] of n integers. He can perform the following operation with the array a no more than n times:

Polycarp selects the index i and adds the value ai to one of his choice of its neighbors. More formally, Polycarp adds the value of ai to ai−1 or to ai+1 (if such a neighbor does not exist, then it is impossible to add to it).
After adding it, Polycarp removes the i-th element from the a array. During this step the length of a is decreased by 1.
The two items above together denote one single operation.

For example, if Polycarp has an array a=[3,1,6,6,2], then it can perform the following sequence of operations with it:

Polycarp selects i=2 and adds the value ai to (i−1)-th element: a=[4,6,6,2].
Polycarp selects i=1 and adds the value ai to (i+1)-th element: a=[10,6,2].
Polycarp selects i=3 and adds the value ai to (i−1)-th element: a=[10,8].
Polycarp selects i=2 and adds the value ai to (i−1)-th element: a=[18].
Note that Polycarp could stop performing operations at any time.

Polycarp wondered how many minimum operations he would need to perform to make all the elements of a equal (i.e., he wants all ai are equal to each other).

Input
The first line contains a single integer t (1≤t≤3000) — the number of test cases in the test. Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤3000) — the length of the array. The next line contains n integers a1,a2,…,an (1≤ai≤105) — array a.

It is guaranteed that the sum of n over all test cases does not exceed 3000.

Output
For each test case, output a single number — the minimum number of operations that Polycarp needs to perform so that all elements of the a array are the same (equal).

Example
inputCopy
4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1
outputCopy
4
2
0
2
Note
In the first test case of the example, the answer can be constructed like this (just one way among many other ways):

[3,1,6,6,2] −→−−−−−−−i=4, add to left [3,1,12,2] −→−−−−−−−−i=2, add to right [3,13,2] −→−−−−−−−−i=1, add to right [16,2] −→−−−−−−−i=2, add to left [18]. All elements of the array [18] are the same.

In the second test case of the example, the answer can be constructed like this (just one way among other ways):

[1,2,2,1] −→−−−−−−−−i=1, add to right [3,2,1] −→−−−−−−−i=3, add to left [3,3]. All elements of the array [3,3] are the same.

In the third test case of the example, Polycarp doesn’t need to perform any operations since [2,2,2] contains equal (same) elements only.

In the fourth test case of the example, the answer can be constructed like this (just one way among other ways):

[6,3,2,1] −→−−−−−−−−i=3, add to right [6,3,3] −→−−−−−−−i=3, add to left [6,6]. All elements of the array [6,6] are the same.

solution

/*
题意：
+ 给出长为n（3e3）的数组，每次可以删去a[i]并把值添加到a[i-1]或a[i+1]。
+ 求最少多少次可以使数组元素全部相等
思路：
+ 因为操作不改变数组总和sum，所以k次运算后每个元素都为sum/(n-k)
+ 因为n较小，所以枚举k,对于给定的k遍历数组，贪心的检查是否能拆分成sum/(n-k)即可。复杂度O(n^2)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 3e3+10;
int a[maxn];
int main(){
	ios::sync_with_stdio(false);
	int T;  cin>>T;
	while(T--){
		int n;  cin>>n;
		LL sum = 0;
		for(int i = 1; i <= n; i++){
			cin>>a[i];  sum += a[i];
		}
		for(int k = n; k >= 1; k--){
			if(sum%k!=0)continue;
			LL cur = sum/k, tmp = 0;
			int ok = 1;
			for(int i = 1; i <= n; i++){
				tmp += a[i];
				if(tmp>cur){
					ok = 0; break;
				}else if(tmp==cur){
					tmp = 0;
				}
			}
			if(ok){
				cout<<n-k<<"\n";
				break;
			}
		}
	}
	return 0;
}

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113482432