和【Light】[1076 ]Get the Containers是一个问题
不过这个在找到最大值的最小值后
需要把组合方式也输出
优先组合前面的数字
需要注意的是
有可能在找完之前就组合完成了
所以后面的就不用再进行组合了
如
1
6 4
10
5
5
5
5
5
5
应该输出
Case 1: 10
10
10
10
5
5
直接判断符合条件的话会全部输出10
这里是记录输出的次数
如果剩余需要输出的次数与剩下的数相等
那么直接输出数字
就不用在进行判断是否组合了
#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);
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);
sum=0;
int cnt=m;
for(int i=0; i<n; i++) {
if(sum+a[i]>res||cnt==n-i+1) {
printf("%d
",sum);
cnt--;
sum=0;
}
sum+=a[i];
}
printf("%d
",sum);
}
return 0;
}