网站建设预算表,河北提供网站制作公司电话,网站做seo收录,浙江网站建设电话有 NNN 堆石子#xff0c;每堆的石子数量分别为 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。
你可以对石子堆进行合并操作#xff0c;将两个相邻的石子堆合并为一个石子堆#xff0c;例如#xff0c;如果 a[1,2,3,4,5]a[1,2,3,4,5]a[1,2,3,4,5]#xff0c;合并第 2,32…有 NNN 堆石子每堆的石子数量分别为 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。
你可以对石子堆进行合并操作将两个相邻的石子堆合并为一个石子堆例如如果 a[1,2,3,4,5]a[1,2,3,4,5]a[1,2,3,4,5]合并第 2,32,32,3 堆石子则石子堆集合变为 a[1,5,4,5]a[1,5,4,5]a[1,5,4,5]。
我们希望通过尽可能少的操作使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解因为可以将所有石子堆合并为一堆。
输入格式 第一行包含整数 TTT表示共有 TTT 组测试数据。
每组数据第一行包含整数 NNN。
第二行包含 NNN 个整数 a1,a2,…,aNa_1,a_2,…,a_Na1,a2,…,aN。
输出格式 每组数据输出一行结果。
数据范围 1≤T≤10,1≤T≤10,1≤T≤10, 1≤N≤105,1≤N≤10^5,1≤N≤105, 0≤ai≤106,0≤a_i≤10^6,0≤ai≤106, ∑i1nai≤106,∑_{i1}^na_i≤10^6,∑i1nai≤106, 每个输入所有 NNN 之和不超过 10510^5105。
输入样例
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0输出样例
3
2
0样例解释 第一组数据只需要用 333 个操作来完成 1 2 3 1 1 1
- 3 3 1 1 1
- 3 3 2 1
- 3 3 3第二组数据只需要用 222 个操作来完成 2 2 3
- 2 5
- 7第三组数据我们什么都不需要做。 #includeiostreamusing namespace std;const int N 100010;typedef long long LL;int n;
int a[N];bool check(LL x){LL sum 0;for(int i 0; i n; i){sum a[i];if(sum x) sum 0;else if(sum x) return false;}return true;
}int main(){int t;scanf(%d, t);while(t--){scanf(%d, n);LL sum 0;for(int i 0; i n; i) scanf(%d, a[i]), sum a[i];for(int i n; ; i--){if(sum % i 0 check(sum / i)){printf(%d\n, n - i);break;}}}return 0;
}
