样例输入

2
5 2
5 3 2 4 1
5 3
5 3 2 4 1

样例输出

8
5

解题思路：二分法，emm……，感觉挺难想到的。

问题简化

给定一个数组，和一个值k，数组分成k段。要求这k段子段和最大值最小。求出这个值。

1、求出数组中的最大值max与数组所有值的和sum，则所求值必在max与sum之间

2、二分思想，将max与sum命为left与right，并不断测试中值，不断二分，最后得到所求值。

Num函数用来记录数组划分不大于mid的划分次数。

（1）如果Num(mid)<=m,小于说明分的段小了（mid数大了），等于继续划分，让k段子段和最大值最小，right=mid

（2）如果Num(mid)>m,大于说明分的段多了（mid数小了），left=mid+1。

参考：

二分法解数组分段和最大值最小问题

#include<stdio.h>
int a[10005]={};
int n,m,i;
int Max(int a[],int n){int i,max=0;for(i=0;i<n;i++){if(a[i]>max)max=a[i];}return max;
}
int Sum(int a[],int n){int i,sum=0;for(i=0;i<n;i++){sum+=a[i];}return sum;
}
//分成和不大于x的分段次数 
int Num(int a[],int n,int x){int num=1,total=0;for(i=0;i<n;i++){total+=a[i];if(total>x){num++;total=a[i];} } return num;
}
//二分查找
int find(int a[],int n,int m){int left=Max(a,n);int right=Sum(a,n);int mid,t;//t为划分最大值为x的划分次数 while(left<right){mid=(left+right)/2;t=Num(a,n,mid);if(t<=m){//说明mid大了 right=mid;} else{left=mid+1;}}return left;
} 
int main(){int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&a[i]);}printf("%d\n",find(a,n,m));}
}