杭州知名网站建设公司免费网站外链推广

有 $N$ 堆石子，每堆的石子数量分别为 $a_1,a_2,\dots ,a_N$。

你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 $a=[1,2,3,4,5]$，合并第 $2,3$ 堆石子，则石子堆集合变为 $a=[1,5,4,5]$。

我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。

请你输出所需的最少操作次数。

本题一定有解，因为可以将所有石子堆合并为一堆。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2,\dots ,a_N$。

输出格式
每组数据输出一行结果。

数据范围
$1\le T\le 10,$
$1\le N\le 10^5,$
$0\le a_i\le 10^6,$
${\sum }_{i=1}^n{a}_i\le 10^6,$
每个输入所有 $N$ 之和不超过 $10^5$。

输入样例：

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

输出样例：

3
2
0

样例解释
第一组数据，只需要用 $3$ 个操作来完成：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

第二组数据，只需要用 $2$ 个操作来完成：

   2 2 3
-> 2 5
-> 7

第三组数据，我们什么都不需要做。

---

#include<iostream>using 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;
}