4366. 上课睡觉

Powered by:NEFU AB-IN

Link

4366. 上课睡觉

• 题意

  有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
  你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
  我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
  请你输出所需的最少操作次数。
  本题一定有解，因为可以将所有石子堆合并为一堆。

• 思路

  约数的二级结论：

  • int范围内，最多的约数有1600个
  • 720720，有240个约数
  • 一个数的约数大约是 logn 个

  先算出整个数组的总和sum，如果要分段，每一段的总和必须是sum的约数，那么就可以枚举sum的每个约数，看符合条件的哪个合成次数最少
  枚举时，从左到右进行挨个枚举，每个数一次加入，如果大于了约数，肯定不成立；等于的话，就清0，继续往右扫

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-01 20:33:22
  * @FilePath: \Acwing\4366\4366.cpp
  * @LastEditTime: 2023-01-01 20:57:14
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define N n + 100
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  #undef int
  
  void solve()
  {
       
      int n;
      cin >> n;
      vector<int> a(n);
      for (int i = 0; i < n; ++i)
          cin >> a[i];
      int sum = accumulate(a.begin(), a.end(), 0);
  
      vector<int> b;
      for (int i = 1; i * i <= sum; ++i)
      {
       
          if (sum % i == 0)
          {
       
              b.push_back(i);
              if (i * i != sum)
                  b.push_back(sum / i);
          }
      }
      if (!SZ(b))
      {
       
          cout << "0\n";
          return;
      }
      sort(b.begin(), b.end());
  
      auto fun = [&](int x) {
       
          int cnt = 0, tmp = 0, flag = 0;
          for (int i = 0; i < n; ++i)
          {
       
              if (flag)
                  cnt++;
              tmp += a[i];
              flag = 1;
              if (tmp == x)
                  tmp = 0, flag = 0;
              if (tmp > x)
                  return INT_MAX;
          }
          return cnt;
      };
  
      int ans = INT_MAX;
      for (auto x : b)
      {
       
          ans = min(ans, fun(x));
      }
      cout << ans << '\n';
      return;
  }
  
  signed main()
  {
       
      IOS;
      int T;
      cin >> T;
      while (T--)
          solve();
      return 0;
  }