UVa 311 - Packets

链接

传送门

题意

有$1 \times 1、2 \times 2、3 \times 3、4 \times 4、5 \times 5、6 \times 6$的盒子,输出把它们放到$6 \times 6$的盒子中最少需要的盒子的个数。

思路

优先考虑大的盒子,$3 \times 3、4 \times 4、5 \times 5、6 \times 6$的盒子不能与更大的放在一起,可以直接计算,$5 \times 5$的可以和11个$1 \times 1$的放在一起,$4 \times 4$的可以和5个$2 \times 2$,$3 \times 3$的分多钟情况考虑,最后将多出来的$2 \times 2$转化为$1 \times 1$的即可。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int c[4][2] = {{0, 0}, {5, 7}, {3, 6}, {1, 5}};
int a[7];
int main() {
while (~scanf("%d%d%d%d%d%d", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6])) {
if (!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) {
break;
}
int ans = a[6] + a[5] + a[4] + (a[3] + 3) / 4;
a[1] -= a[5] * 11;
a[2] -= a[4] * 5;
a[1] -= c[a[3] % 4][1];
a[2] -= c[a[3] % 4][0];
if (a[2] > 0) {
int t = (a[2] + 8) / 9;
ans += t;
a[2] -= t * 9;
}
a[1] += a[2] * 4;
if (a[1] > 0) {
ans += (a[1] + 35) / 36;
}
printf("%d\n", ans);
}
return 0;
}