把n个数划分m组
找出所有可能的和的最大值里面的最小值
二分思想
在 l~r 的区间里查找结果
#include<stdio.h>
int a[1200];
int n,m;
bool judge(int t) {
int cnt=1;
int sum=0;
for(int i=0; i<n; i++) {
if(sum+a[i]>t) {
cnt++;
sum=0;
}
sum+=a[i];
}
if(cnt<=m)
return true;
else
return false;
}
int main() {
int T,kase=0;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&m);
int max=0,sum=0;
for(int i=0; i<n; i++) {
scanf("%d",&a[i]);
sum+=a[i];
if(max<a[i])
max=a[i];
}
int l=max,r=sum;
int res=max;
while(r>=l) {
int mid=(l+r)/2;
if(judge(mid)) {
res=mid;
r=mid-1;
} else
l=mid+1;
}
printf("Case %d: %d
",++kase,res);
}
return 0;
}