二分答案

洛谷 P1182 数列分段 Section II

题目链接:https://www.luogu.com.cn/problem/P1182

题目描述:

题目

思路:

我们要找的答案是(将长度为n的数组,分成m段,每一小段求和,取最大值,)从满足要求的所有划分情况中找最小的最大值。如果要求划分为一段,那么最大值就是这个数组每一位的和(答案的最大值 r),如果划分为n段(一段只有一个元素),则最大值为数组中元素的最大值(答案的最小值 l)。mid为答案的中间值,使得划分出来的每一小段的和小于等于这个mid,(则此种划分得最大值为mid),我们可以获得这个答案下数组被划分为了几段(dun),dun<m意味着最终的答案比mid小(答案在[l,mid-1]r=mid-1),反之最终的答案比mid大。不断缩小(l,r)的范围,最终可获得结果。

代码:

#include<iostream>
#include<stdio.h>
using namespace std;
int n,m;
int mid,l,r;
const int maxn=1e5+5;
int a[maxn];
int sum,dun;
bool judge(int mid,int a[]){

    for(int i=1;i<=n;i++){
        if(sum+a[i]<=mid) sum+=a[i];
        else sum=a[i],dun++;
    }
    return dun<m;        //所分段落数目小于要求划分的段落数m,此时的所得的最大值还不是最小的
}
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d%d",&n,&m);
    l=r=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        l=max(l,a[i]);
        r+=a[i];
    }

    while(l<=r){
        mid=(l+r)/2;

        sum=dun=0;
        if(judge(mid,a))r=mid-1;          //此时的mid还偏大
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}
Last modification:December 10th, 2019 at 12:23 am
如果觉得我的文章对你有用,请随意赞赏