解题报告 P1182 数列分段 Section II

题目内容

P1182

大意：给出一个序列，要求分成 m 段，求每段和的最大值的最小值

解题思路

一看到“最大的最小”就知道这题需要使用二分答案。首先判断他的单调性：很明显，我们如果设定每段和的最大值越大，需要划分的段数就越小，相反的，如果我们设定每段和的最大值越小，需要划分的段数就越多，以此性质来进行二分答案。

至于如何判断，就需要使用前缀和，具体见代码的 check 函数。

#include <cstdio>

const int maxn=1e5+5;
int n,m,a[maxn],sum[maxn];

bool check(int mid)
{
    int cnt=0,lastans=1;//cnt为切的刀数，lastans为新一段的起点
    for(int i=1;i<=n;i++)//开始扫描
    {
        if(sum[i]-sum[lastans-1]>mid)//如果[lastans,i]的和大于设定的最大值
        {
            cnt++;//那么就只取[lastans,i-1]
            lastans=i;//i成为新的lastans
        }
    }
    return cnt+1<=m;//由于cnt是刀数，判断的时候要+1
}

int main()
{
    scanf("%d %d",&n,&m);
    int maxa=0;//序列中元素的最大值，以此为左端点进行二分
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        sum[i]=sum[i-1]+a[i];
        maxa=maxa<a[i]?a[i]:maxa;
    }
    int l=maxa,r=sum[n],ans;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))//如果能行，就说明mid可以再小一点
        {
            ans=mid;
            r=mid;
        }
        else
            l=mid+1;
    }
    printf("%d\n",ans);
}

总的时间复杂度为 O(n\log n)