P1182 数列分段 Section II

经典的二分答案：段和最大值最小为多少

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005];
bool judge(long long mid){
    long long sum=a[1],cnt=1;
    for(int i=2;i<=n;i++){
        if(sum+a[i]<=mid){
            sum+=a[i];
        }
        else{
            sum=a[i];
            cnt++;
            if(cnt>m) return false;
        }
    }
    return true;
}
int main(){
    cin>>n>>m;
    long long l=0,r=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(l<a[i]) l=a[i];
        r+=a[i];
    }
    long long ans=0;
    while(l<=r){
        long long mid=l+(r-l>>1);
        if(judge(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}