[USACO22FEB] Sleeping in Class B 题解

Zirnc · 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;
}