题目描述
对于给定的一个长度为N的正整数数列 A-iA−i ，现要将其分成 M(M≤N)M(M≤N) 段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 142451 要分成 33 段
将其如下分段：
[4 2][4 5][1][42][45][1]
第一段和为 6 ，第 2 段和为 9 ，第 3 段和为 1 ，和最大值为 9 。
将其如下分段：
[4][2 4][5 1][4][24][51]
第一段和为 4 ，第 2 段和为 6 ，第 3 段和为 6 ，和最大值为 6 。
并且无论如何分段，最大值不会小于 66 。
所以可以得到要将数列 4 2 4 5 142451 要分成 3 段，每段和的最大值最小为 6 。
输入输出格式
输入格式：
第 1 行包含两个正整数N，M。
第 22行包含 NN 个空格隔开的非负整数 Ai ，含义如题目所述。
输出格式：
一个正整数，即每段和最大值最小为多少。
输入输出样例
5 3
4 2 4 5 1
6
说明
对于 20\%20% 的数据，有 N≤10N≤10 ；
对于 40\%40% 的数据，有 N≤1000N≤1000 ；
对于 100\%100% 的数据，有 N≤100000,M≤N, Ai,Ai 之和不超过 10^9 。
这个题时一个典型的二分答案（最大的最小、最小的最大）
首先根据题意，我们确定段的最大值一定在整个数组的最大值和10^9之间，因此做如下定义
l = maxn, r = 1000000000;
然后我们确定好一个mid = （l+r）>> 1，表示最大值为mid时是否可行；
下面就进行二分的正常过程，判断
然后遍历整个数列，记录下一个tot，表示这个数列中最大值不超过mid时，需要分成的段数，用now来代表当前段的和
now+a[i]<mid时：可以继续加，这个段还没有结束
now+a[i]==num时：说明当前段已经达到了最大值，记下这个段（tot++），now=0，以便分析下一个段
now+a[i]>num时：说明这个段加上a[i]之后超过mid，就不能加上这个a[i]，那么这个段已经计算完（tot++），a[i]算到下一个段内
如果tot<m,说明要达到当前的段数m，mid的值必须要降低，这样才能使段数增多，收缩右边界；
否则，改变左边界。
附上代码（亲测AC）
#include<iostream>
#include<cmath>
using namespace std;
const int MAXN=;
int maxn = -;
int n, m, a[];
int l = maxn, r = ;
int judge(int num){
int now = ;
int tot = ;
for(int i=;i<=n;i++){
if(now+a[i]<num){
now += a[i];
}
else if(now+a[i]==num){
now = ;
tot++;
}
else if(now+a[i]>num){
now = a[i];
tot++;
}
}
if(now) tot++; //如果还有剩余的一个值，那么这个单独算一个段
if(tot>m)return ;
else return ; } int main(){
cin >> n >> m;
for(int i=;i<=n;i++) {
cin >> a[i];
maxn = max(a[i], maxn);
}
int l = maxn, r = ;
if(n==m){
cout << maxn;
return ;
}
while(l<r){
int mid = (l+r) >> ;
if(judge(mid)==){
r = mid;
}
else{
l = mid + ;
}
}
cout << r;
return ;
}