自动搬运

查看原文

来自洛谷，原作者为

	Zirnc afo

搬运于2025-08-24 22:36:41，当前版本为作者最后更新于2022-03-05 10:34:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（参考 USACO 官方题解）

关键点是发现：不论怎么改变数组，它的元素总和总是不变的。

通过枚举处理后的数组的长度 $r$，我们可以知道每一段的和 $\frac{\text{sum}(a)}{r}$。判断这个和是不是整数，再检验一下能不能凑出这个和就可以了。

时间复杂度：$O(N \cdot (\#\text{sum}(a)\text{ 因子个数 }))$

int a[1000006];
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      sum += a[i];
    }
    int ans;
    for (int i = n; i >= 1; i--) { // r
      if (sum % i != 0)
        continue;
      int cur = 0;
      bool flag = 1;
      for (int j = 0; j < n; j++) {
        cur += a[j];
        if (cur > sum / i) {
          flag = 0;
          break;
        } else if (cur == sum / i) {
          cur = 0;
        }
      }
      if (flag) {
        ans = n - i;
        break;
      }
    }
    cout << ans << endl;
  }
  return 0;
}