Codeforces Round #826 (Div. 3) C

「爱情、让人受尽委屈。」 2024-03-31 13:58 64阅读 0赞

[Problem - C - Codeforces][]

题意：

给定一个长度为n的数组，求将该数组分为连续的几个部分，使得每一部分内部的和相同。求分完后每一部分的最大值最小。

思路：

一开始看到最大值最小，想到去二分这个部分和，但是很快发现它并不满足单调性，部分和必须是数组和的因子

二分不行，我们考虑去枚举数组和的因子，因为数组和不会很大，因此枚举因子是可行的

对于枚举到的一个因子，我们去check，然后对于每一次枚举都取维护最大值

在check函数里直接模拟就行，如果刚好等于就维护一下最大值，如果太大就返回不合法

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10,mnf=0x3f3f3f3f;
    int n,ans=mnf;
    int a[mxn],b[mxn];
    int calc(int x){
        int cur=0,len=0,res=0;
        for(int i=1;i<=n;i++){
            cur+=a[i];
            len++;
            if(cur==x){
                res=max(res,len);
                cur=len=0;
            }else if(cur>x) return 0;
        }
        return res;
    }
    void init(){
        ans=mnf;
        memset(b,0,sizeof(b));
    }
    void solve(){
        scanf("%d",&n);
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=b[i-1]+a[i];
        }
        int sum=b[n];
        for(int i=1;i*i<=sum;i++){
            if(sum%i==0){
                int tmp=calc(i);
                if(tmp) ans=min(ans,tmp);
                tmp=calc(sum/i);
                if(tmp) ans=min(ans,tmp);
            }
        }
        printf("%d\n",ans);
    }
    int main(){
        int T;
        scanf("%d",&T);
        while(T--)solve();
        return 0;
    }

**总结：**

**这题最重要的是发现这并不单调，不能进行二分，因为需要满足每段之和必须是数组和的因子，认识到这点很重要**

**二分不行，我们就去考虑枚举，考虑枚举的时候，注意去观察枚举的东西需要满足什么条件**

[Problem - C - Codeforces]: https://codeforces.com/contest/1741/problem/C