Problem F: D
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 178 Solved: 38
Submit Status Web Board
Description
晴天想把一个包含n个整数的序列a分成连续的若干段，且和最大的一段的值最小，但他有强迫症，分的段数不能超过m段，然后他就不会分了。。。他想问你这个分出来的和最大的一段的和最小值是多少？
Input
第一行输入一个整数t，代表有t组测试数据。
每组数据第一行为两个整数n,m分别代表序列的长度和最多可分的段数。
接下来一行包含n个整数表示序列。
0<=n<=50000 1<=m<=n，0<=ai<=10000。
Output
输出一个整数表示和最大的一段的最小值。
Sample Input
1
3 2
1 3 5
Sample Output
5
HINT
1 3 5 分成一段可以为1 3 5和为9，分成两段可以为1，3 5或者1 3，5，和最大的一段值分别为8，5，所以答案为5
用二分判断每个长度是否可行
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[50002];
int n,m;
bool judge(int mid)
{int duan=0,he=0;for(int i=0;i<n;i++){if(he+a[i]>mid)//如果当前值加上该序列的和大于mid,记录当前值。再开一个序列； {duan++;//分的段数； he=a[i];}elsehe+=a[i];//延长该段； }if(he>0)duan++;if(duan<=m)return true;return false;
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int sum=0,l=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);l=max(l,a[i]);sum+=a[i];}int r=sum,ans=0;while(l<=r){int mid=(l+r)/2;if(judge(mid)){ans=mid;r=mid-1;:}else{l=mid+1;}}printf("%d\n",ans);}return 0;
}