问题描述
问题分析
和【Light】[1076 ]Get the Containers是一个问题
不过这个在找到最大值的最小值后
需要把组合方式也输出
优先组合前面的数字
需要注意的是
有可能在找完之前就组合完成了
所以后面的就不用再进行组合了
如
1
2
3
4
5
6
7
8
9
| 1
6 4
10
5
5
5
5
5
5
|
应该输出
1
2
3
4
5
6
| Case 1: 10
10
10
10
5
5
|
直接判断符合条件的话会全部输出10
这里是记录输出的次数
如果剩余需要输出的次数与剩下的数相等
那么直接输出数字
就不用在进行判断是否组合了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #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\n",++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\n",sum);
cnt--;
sum=0;
}
sum+=a[i];
}
printf("%d\n",sum);
}
return 0;
}
|
题目地址:【Light】[1048]Conquering Keokradong