题解 CF1462D 【Add to Neighbour and Remove】

Natsume_Rin · 2020-12-19 15:09:42 · 题解

题意：给出一个长度为 n 的序列 a_1,a_2,a_3\dots a_n，用最少的合并次数，将所有数变为一个相同的数。

观察，我们定义一个变量 sum=\sum_i a_i。

那么最后的结果将所有的数字变为一个数字 k，必须满足 k | sum。

所以我们可以用 O(n) 枚举一个数字 sum/k。以此，可以计算出 k 的值。再用 O(n) 检查是否合法，如果合法就更新答案，否则跳过。

总时间复杂度 O(n^2)。

代码：

#include<bits/stdc++.h>
#define RI register int
using namespace std;
int t;
int n;
const int MAXN = 3005;
int a[MAXN];
int sum;
int ans;
int cnt;
int now;
int main(){
        cin>>t;
        while(t--){
                sum=0;
                cin>>n;
                for(RI i=1;i<=n;++i){
                        cin>>a[i];
                        sum+=a[i];
                }
                ans=n;
                for(RI j=1;j<=n;++j) {
                        if(sum%j==0){
                                cnt=0;
                                now=0;
                                for(RI i=1;i<=n;++i){
                                        if(now==0) cnt--;
                                        now+=a[i];
                                        cnt++;
                                        if(now<sum/j) continue;
                                        if(now>sum/j){
                                                cnt=2147483647;
                                                break;
                                        }
                                        if(now==sum/j) now=0;
                                }
                                ans=min(ans,cnt);
                        }
                }
                cout<<ans<<endl;
        }
}