题目描述
有 $N$ 堆石子，每堆的石子数量分别为 $a _ 1, a _ 2, \cdots, a _ N$。
你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 $a = [1, 2, 3, 4, 5]$，合并第 $2, 3$ 堆石子，则石子堆集合变为 $a = [1, 5, 4, 5]$。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。
本题一定有解，因为可以将所有石子堆合并为一堆。
输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $N$。
第二行包含 $N$ 个整数 $a _ 1, a _ 2, \cdots, a _ N$。
输出格式
每组数据输出一行结果。
数据范围
$1 \le T \le 10,$
$1 \le N \le 10 ^ 5,$
$0 \le a _ i \le 10 ^ 6,$
$\sum \limits _ {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
第三组数据，我们什么都不需要做。
形式化题意
给你一个长度为 $n$ 的数组 $a$，相邻的两个元素可以合并成一个元素。设合并完每个元素都相等的数组 $a ^ \prime$ 长度为 $n ^ \prime$，求 $\min \{n - n ^ \prime\}$。
解题思路
注意到 $\sum \limits _ {i = 1} ^ n a _ i \le 10 ^ 6$，记 $sum = \sum \limits _ {i = 1} ^ n a _ i \le 10 ^ 6$，我们可以枚举合并完每个元素都是 $x$ 使得 $x | sum$。由于 $sum$ 不大，所以 $x$ 的枚举次数不会太多。
枚举完 $x$，我们可以将 $a$ 数组扫一遍检查是否可以划分为连续的 $n ^ \prime = {sum \over x}$ 段使得每段之和都为 $x$，可以则更新答案。
AC Code
#include <iostream>
#define inf 2e9
#define N 100005
using namespace std;
int T, n, sum, ans, a[N];
int main ()
{
ios :: sync_with_stdio (0), cin.tie (0), cin >> T;
while (T --)
{
cin >> n, sum = 0, ans = 0;
for (int i = 1; i <= n; i ++)
{
cin >> a[i], sum += a[i]; // 计算和
}
for (int i = 1, flag = 1; i <= sum; i ++, flag = 1)
{
if (sum % i || sum / i > n) // 如果不能整除或 n' > n
{
continue;
}
for (int j = 1, pos = 0, now = 0; j <= sum / i; j ++, now = 0)
{
while (pos < n && now < i) // 在合法且当前段的和 < x 时
{
now += a[++ pos]; // 当前段的和加上这一元素
}
if (now != i) // 如果太多或太少
{
flag = 0; // 不可行，退出
break;
}
}
if (flag)
{
ans = n - sum / i; // 更新答案，这时答案一定是最小的，退出
break;
}
}
cout << ans << endl;
}
return 0;
}
感谢观看！
$$\href {/blog/content/29204/} {\color {Lime} {【寒假每日一题】题解}}$$
