题目内容

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)

最后修改日期:2020年3月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。