Acwing-4366. 上课睡觉

假设最终答案为每堆石子均为cnt个，cnt一定可以整除sum（石子的总数），我们可以依次枚举答案。sum小于等于10^6，所以cnt的数量等于sum约数的个数，10^6范围内，约数最多的数为720720，它的约数个数有240个，int范围内(2147483647)，约数个数最多有1600个。

我们可以枚举每一个cnt的取值能否取到，然后在所有可以取到的范围里面，找到一个操作数量方案最少的一个，最后每一堆石子的个数是cnt个的话，则一共有sum / cnt 堆，初始的时候有n堆，每操作一次会减少一堆，所以我们最终的操作数量是n - (sum / cnt)，我们希望这个数越小越好，所以应该让cnt越小越好，所以本题我们就是要找到一个最小的cnt（cnt为最终每一堆石子的数量），使得可以取到。所以，我们可以从小到大枚举cnt，看看成不成立就可以了。

本题一定是有解的，最坏情况下，cnt取到sum，n堆石子合并为1堆。

接下来，思考一下如何判断cnt是否成立？（即判断最后能否将每堆石子的数量变成cnt）

本题每次石子合并只能合并相邻两堆，最后每一堆在原始序列中应该是连续的一段，此时问题等价于能否将序列分成若干段，使得每一段中所有数的和是cnt

 那如何判断能否将序列分成若干段，使得每一段中所有数的和是cnt呢？

我们可以从前往后考虑，先看第一段，第一段我们从前往后枚举，逐步将每一堆加到第一段里，在枚举的过程中我们维护一下当前的总和是多少，当当前总和s < cnt时，意味着当前总和不够cnt，就必须再添加新的元素，直到第一段的总和>=cnt为止

如果加完每一堆后，石子总数>cnt了，那就表示一定无解，因为去掉一堆则小于cnt，一定不够，加一堆则大于cnt，这就意味着第一段的总和一定不可能是cnt。

如果当前石子总和=cnt，下一堆是0，可以加上，下一堆不是0，就不能加了，如果发现当前段石子的总和=cnt了，就可以去枚举下一段，依次去计算每一段能不能凑出来cnt，如果全部能凑出来的，表明cnt是合法的，否则表示cnt不合法。

判断cnt是否合法，从前往后扫描每一段，只要当前这一段总和小于cnt就一直加，直到加到>=cnt为止，如果大于cnt就无解，如果等于cnt则表示这一段枚举完了，再继续枚举下一段，每一次判断cnt是否成立需要O(n)次，我们一共最多有240个约数备选，所以计算量总共是240*n。

我们可以枚举最后每一堆的个数，也可以枚举堆数，最后的堆数越多，则减少的堆数就越少，操作数量就越少，每一堆的数量是总和的约数，那么堆数也是总和的约数，因为每一堆的数量*堆数=总和

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int w[N];
int n;

bool check(int k)
{
    int s = 0;
    for (int i = 0; i < n; ++ i)
    {
        s = s + w[i];
        if (s > k) return false;
        if (s == k) s = 0;
    }
    return true;
}

int main()
{
    int t;
    scanf("%d", &t);
    
    while (t --)
    {
        scanf("%d", &n);
        
        int sum = 0;
        for (int i = 0; i < n; ++ i)
        {
            scanf("%d", &w[i]);
            sum += w[i];
        }
        
        for (int i = n; i > 0; -- i)
        {
            if (sum % i == 0 && check(sum / i))
            {
                printf("%d\n", n - i);
                break;
            }
        }
    }
    
    return 0;
}