数列分段Section II

二分答案 
题意：    将 n 个 数 分为 m段 求一种方案，使这m段中最大的和 最小 
　　　　其实就是说每一种方案，都有对应的 每段和的最大值，
　　　　要求一种方案，使最大值最小

题解 ：二分答案 mid为分成的最大值， 
然后O(n) 判断 答案 是否可行 
贪心的做下去，如果再加上就要超过了，那就新开一段

最后判断开的段数是否小于 m

1、注意要判断 如果当前这个值大于 mid，一个值就已经大于 mid了，那就直接退出
了，否则 ，这个值也只会单独算为一段的，其实他一段都放不下

2、或者还有这种方法： 答案从 最大的 a[ i ] 开始枚举

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std ; 

const int maxn = 100011 ; 
int n,m,l,r,mid ; 
int a[maxn] ; 

inline bool check( int mid ) 
{
    int ans = 0,sum = 0 ; 
    for(int i=1;i<=n;i++) 
    {
        if(a[ i ]>mid) return 0 ;  
// 1、注意要判断  如果当前这个值大于 mid，一个值就已经大于  mid了，
//那就直接退出了，否则 ，这个值也只会单独算为一段的，其实他一段都放不下 
        if( sum+a[ i ] > mid ) 
            ans++,sum = 0 ;  
        sum+=a[ i ] ; 
    }
    ans++ ; 
    return ans <= m ;  
}

int main() 
{
    scanf("%d%d",&n,&m) ; 
    for(int i=1;i<=n;i++) scanf("%d",&a[ i ]) ; 
    l = 0,r = 1e9 ; 
    while( l<r ) 
    {
        mid = ( l+r )>>1 ;
        if(check(mid)) 
            r = mid ; 
        else  
            l = mid + 1 ;
    }
    printf("%d
",r) ; 
    return 0 ; 
}