数列分段 II

https://loj.ac/problem/10014

题目描述

  给出一个长度为(N)的正整数数列(A)，要求将它分为连续的(M)段，求每段值得最大值最小

思路

  最值中的最值，典型二分题。二分答案，判断在这个答案下能否将数列(A)分为(M)段即可。

  （update 2019.10.25）好吧写博客时想的太简单，有一点需要注意，就是如果一个数已经大于二分的(mid)时显然不行。

代码

#include <bits/stdc++.h>
using namespace std;
int m,n;
int a[101000];
bool check(int x)
{
    int s=0,sum=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>x)return 0;
        s+=a[i];
        if(s>x)
        {
            s=a[i];
            sum++;
        }
    }
    return sum<=m;
}
int main() 
{
//    freopen("aa.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int l=0,r=1e9,ans;
    while(l<r)
    {
        int mid=(r+l)>>1;
//        cout<<r<<' '<<check(mid)<<' '<<l<<endl;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);
    return 0;
}