P8183 [USACO22FEB] Sleeping in Class B 题解

题目大意

一共有 $T$ 组数据，每组数据给定一个长度为 $n$ 的数列。你可以在数列上进行任意次操作，每次操作可以合并相邻的两个数。求最少操作次数使数列的每个数都相等。

思路

正向求最小操作次数很难，但我们反向可以穷举合并过后的数列长度 $k$。

易知无论怎么操作数列总和 $sum$ 都不变。所以我们可以知道，要想使合并后的每个数都相等，$\frac{sum}{k}$ 一定是一个整数，所以我们只要穷举 $sum$ 的所有质因子就可以了，设 $m$ 为 $sum$ 质因子总数。之后我们可以 $O(n)$ 遍历整个数列，使所有的数都合并成 $\frac{sum}{k}$，判断是否可行就可以了。

总复杂度为 $O(T\cdot n\cdot m)$，足以通过本题。详见代码。

代码

#include <bits/stdc++.h>
using namespace std;
int T,n,a[100001],sum,sumT;
int main()
{
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        cin>>n;sum=0;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];sum+=a[j];
        }
        for(int j=n;j>=1;j--)//穷举合并后的数列长度
        {
            if(sum%j==0)
            {
                sumT=sum/j;//每个数的值
                int pre=0;bool ok=1;
                for(int k=1;k<=n;k++)//判断是否可行
                {
                    pre+=a[k];
                    if(pre>sumT){ok=0;break;}
                    else if(pre==sumT)pre=0;
                }
                if(ok==1){cout<<n-j<<endl;break;}
            }
        }
    }
    return 0;
}