D. Add to Neighbour and Remove （枚举）

D. Add to Neighbour and Remove （枚举）

链接

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
input
4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1
output
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.

题意
你可以将序列中的数向两个相邻的数依附，即加上这个数，然后删了这个数，求序列数字都相同的最小步数。

思路
从结果来考虑，我们将序列中最大的数到所有的和所有能整除和的数判断一边就行，模拟看下对不对，对就输出
3000的数据量，n^2随便过！

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double esp = 1e-6;
const double PI = acos(-1);
const int N = 1e5 + 5;int n,m,x; 
int a[N]; 
string s;
void solve(){	scanf("%d",&n);int maxx = 0,sum = 0;for(int i=1;i<=n;i++){scanf("%d",&x);a[i]=x;sum += x;maxx = max(maxx, x);}for(int i=maxx;i<=sum;i++){if(sum%i==0){bool flag = true;for(int j=1;j<=n;j++){if(a[j]<i){int summ = 0;for(int k=j;k<=n;k++,j++){summ+=a[k];if(summ == i) break;if(summ > i){flag = false;break;} }} }if(flag){printf("%dn",n-sum/i);return;}}}
}int main(){int t = 1;scanf("%d",&t);while(t--){solve();}return 0;
}
/*
5 0 3 0 4
5 5 3 5 4
*/