题目大意
把一个长度为n数列分成m段，让每段的最大值最小。(m<=n)
题目分析
首先看出这题应该用二分做，然后考虑这道题答案范围的上下限：下限就是最大的\(a_i\)，而上限就是\(\Sigma^{i=n}_{i=1}a_i\)
确定边界之后，开始二分：
用当前的mid作为每一段的最大值，假如能够将该数列分为m段，那么r=mid,那么r=mid，否则l=mid+1;
#include<iostream>
#include<cstdio>
#define sco 100010
using namespace std;
int n,m,l(0),r(0),a[sco];
bool check(int t){
int sum=0,cnt=1;
for(int i=1;i<=n;++i){
if(sum+a[i]<=t)sum+=a[i];
else {sum=a[i];++cnt;}
}
return cnt<=m;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",a+i);l=max(l,a[i]);
r+=a[i];
}
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;else l=mid+1;
}
printf("%d",l);
return 0;
}