装箱问题

形式化题目

有六种方形产品，边长分别为 $1,2,3,4,5,6$ ，高度都等于包裹高度 $h$ 。每个包裹是 $6 \times 6 \times h$ 的长方体。因为高度相同，三维问题退化成二维：每个包裹就是一张 $6 \times 6$ 的方格纸，要把若干个边长为 $1 \sim 6$ 的正方形不重叠地放进去。

输入是若干行，第 $i$ 行为

c_1\ c_2\ c_3\ c_4\ c_5\ c_6,

其中 $c_k$ 表示边长为 $k$ 的正方形个数（ $1 \leqslant k \leqslant 6$ ）。以 0 0 0 0 0 0 一行表示输入结束，该行不产生输出。对每个订单，求装下全部产品所需的最少包裹数，每行输出一个整数。

样例的两个订单分别是 $c_3 = 4, c_6 = 1$ （答案 $2$ ）和 $c_1 = 7, c_2 = 5, c_3 = 1$ （答案 $1$ ）。

正解

思路

从最大的开始放，能定下来的先定下来。 关键观察是：

边长 $6$ 的正方形正好铺满一整箱，一个 $6$ 必须独占一个包裹；
边长 $5$ 的正方形占掉一整行还剩一条宽 $1$ 的缝，只能放 $1 \times 1$ ，放不下任何 $2 \times 2$ ；
边长 $4$ 的正方形占掉一整条 $4 \times 6$ ，剩下 $2 \times 6 = 12$ 格，最多放 $5$ 个 $2 \times 2$ （ $12$ 格放不下 $6$ 个，因为每个 $2 \times 2$ 占 $4$ 格且需要成对的行列）；
边长 $3$ 的正方形一箱最多放 $4$ 个（ $2 \times 2$ 排列），所以 $3 \times 3$ 的数量每四个凑一箱。

于是贪心分三层：

第一层：大件定箱数。 $6$ 、 $5$ 、 $4$ 各占一个包裹， $3$ 每四个占一个：

\text{boxes} = c_6 + c_5 + c_4 + \left\lceil \frac{c_3}{4} \right\rceil .

第二层：算已开包裹里还剩多少 $2 \times 2$ 的槽位。 由上面的观察：

每个 $5 \times 5$ 旁边能放 $0$ 个 $2 \times 2$ （只有 $1$ 宽的缝）；
每个 $4 \times 4$ 旁边能放 $5$ 个；
装 $3 \times 3$ 的箱子里放完 $k = c_3 \bmod 4$ 个 $3 \times 3$ 后（ $k = 0$ 表示这一箱被 $4$ 个 $3 \times 3$ 占满），剩下的空间能放多少个 $2 \times 2$ 如下表：

$k$ （该箱里的 $3 \times 3$ 个数）	0	1	2	3
剩余可放 $2 \times 2$ 个数	0	5	3	1

即 two_slots = 5 * c4 + LEFT_FOR_TWO[c3 % 4]。注意： $3 \times 3$ 只影响最后那一箱的余数，前面被 $4$ 个 $3 \times 3$ 占满的箱子没有任何槽位，所以只需查 $c_3 \bmod 4$ 。

$2 \times 2$ 用不完这些槽位就再开新箱，每箱最多 $9$ 个：

\text{boxes} \mathrel{+}= \left\lceil \frac{\max(0,\; c_2 - \text{two\_slots})}{9} \right\rceil .

第三层： $1 \times 1$ 用总面积兜底。 前两层结束后，所有包裹的总面积是 $36 \cdot \text{boxes}$ 。 $6 \times 6$ 、 $5 \times 5$ 、 $4 \times 4$ 、 $3 \times 3$ 、 $2 \times 2$ 已经占掉的面积分别是 $36, 25, 16, 9, 4$ 倍。于是

\text{one\_slots} = 36 \cdot \text{boxes} - 36c_6 - 25c_5 - 16c_4 - 9c_3 - 4c_2,

它就是所有包裹加起来还能放下的 $1 \times 1$ 个数。不够就继续开新箱，每箱 $36$ 个：

\text{boxes} \mathrel{+}= \left\lceil \frac{\max(0,\; c_1 - \text{one\_slots})}{36} \right\rceil .

为什么贪心是对的？ 每一步的选择都是被迫的，可以用交换论证说明：

$6 \times 6$ 放不下第二个任何型号，必须独占； $5 \times 5$ 与 $4 \times 4$ 同理不能与同尺寸或更大的共箱，所以 $c_6 + c_5 + c_4$ 是硬下界，且取到这个下界不会挤掉任何更小的产品（它们只占用"剩余空间"，而剩余空间无论如何都用不完）。
每个 $3 \times 3$ 必须占一整行或一整列的 $3$ 格条带，一箱最多容纳 $4$ 个，所以 $\lceil c_3 / 4 \rceil$ 也是硬下界。既然箱数已由 $1$ 定死， $3 \times 3$ 就按 "每箱塞满 $4$ 个、最后一箱留 $k$ 个"摆放，这时留出的 $2 \times 2$ 槽位最多。
$2 \times 2$ 只用已开箱的槽位是免费的，能塞就塞；塞不下的部分只能开新箱，每箱 $9$ 个又是硬上界，所以 $\lceil \cdot / 9 \rceil$ 最优。
最后 $1 \times 1$ 是最小单位，任何空位都能填，按总面积计算既不会浪费也不会冲突。

三层各自取到下界，且互不抢占对方的必要空间，所以累加结果即最小包裹数。

样例追踪。 对订单 0 0 4 0 0 1：第一层 $\text{boxes} = 1 + 1 = 2$ （ $c_3 = 4$ 恰好一箱、 $c_6 = 1$ 一箱）；two_slots = 0； $c_2 = 0$ 不加箱；one_slots = 72 - 36 - 36 = 0， $c_1 = 0$ 不加箱，答案 $2$ 。对订单 7 5 1 0 0 0：第一层 $\text{boxes} = \lceil 1/4 \rceil = 1$ ；two_slots = LEFT_FOR_TWO[1] = 5，恰好放下 $5$ 个 $2 \times 2$ ；one_slots = 36 - 9 - 4 \times 5 = 7， $c_1 = 7$ 刚好用完，答案 $1$ 。

代码

Python 版：

python

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
58
59#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:39
# update_at: 2026-10-07 15:39

import sys
from itertools import islice

# 一箱里放 k 个 3*3（k = 0,1,2,3）之后，还能塞下的 2*2 个数
LEFT_FOR_TWO = (0, 5, 3, 1)

END = (0, 0, 0, 0, 0, 0)  # 输入结束标志：六个 0 的一行
ORDER_LEN = 6                # 每个订单占 6 个整数（1*1 到 6*6）

# 类型别名（Python 3.12+ 的 type 语句），相当于 C++ 的 using / typedef
type Order = tuple[int, ...]  # 一个订单的六个型号数量（1*1 到 6*6）


def ceil_div(a: int, b: int) -> int:
    """向上取整的整数除法。"""
    return -(-a // b)


def min_boxes(order: Order) -> int:
    """求一个订单所需的最小包裹数。"""
    c1, c2, c3, c4, c5, c6 = order

    # 6*6、5*5、4*4 各占一个包裹，3*3 每四个占一个
    boxes = c6 + c5 + c4 + ceil_div(c3, 4)
    # 已开的箱子里被大件腾出来的 2*2 槽位：5*5 旁只能放 1*1，4*4 旁能放 5 个，
    # 3*3 按每箱剩余 0/1/2/3 个分别是 LEFT_FOR_TWO 里的 0/5/3/1
    two_slots = 5 * c4 + LEFT_FOR_TWO[c3 % 4]
    # 槽位不够就再开新箱（每箱 9 个 2*2），够则为 0
    boxes += max(0, ceil_div(c2 - two_slots, 9))
    # 总面积扣掉大件已占的面积（36/25/16/9/4 对应 6*6 ~ 2*2），剩下的全归 1*1
    one_slots = 36 * boxes - 36 * c6 - 25 * c5 - 16 * c4 - 9 * c3 - 4 * c2
    # 剩余空间不够就再开新箱（每箱 36 个 1*1）
    boxes += max(0, ceil_div(c1 - one_slots, 36))
    return boxes


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        order = tuple(islice(data, ORDER_LEN))  # 一次读满一个订单
        if not order or order == END:   # 六个 0 是结束标志，不产生输出
            break
        out.append(str(min_boxes(order)))

    # 全空输入（只有结束行）不输出任何字符
    sys.stdout.write('\n'.join(out) + ('\n' if out else ''))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:39
 * update_at: 2026-10-07 15:39
 */

// 装箱问题：6*6*h 的包裹里塞 1*1 ~ 6*6 的六种方形产品，求最小包裹数。
// 思路：每种产品都占满包裹的高度，问题退化成二维的 6*6 方格切割，
//       大件（4*4 及以上）必须单独占一个包裹，3*3 每四个一箱，剩下的空位才用 1*1、2*2 填。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// left_for_two[k] = 一箱里放 k 个 3*3（k = 0..3）之后，还能塞下的 2*2 个数
int left_for_two[4] = {0, 5, 3, 1};

// 循环处理每个订单：读入六个型号的数量，输出最小包裹数
int main() {
    ll cnt1, cnt2, cnt3, cnt4, cnt5, cnt6;

    while (cin >> cnt1 >> cnt2 >> cnt3 >> cnt4 >> cnt5 >> cnt6) {
        if (cnt1 == 0 && cnt2 == 0 && cnt3 == 0 && cnt4 == 0 && cnt5 == 0 && cnt6 == 0) {
            break;  // 六个 0 是输入结束标志，不产生输出
        }

        // 第一步：6*6、5*5、4*4 各占一个包裹，3*3 每四个占一个
        ll boxes = cnt6 + cnt5 + cnt4 + (cnt3 + 3) / 4;

        // 第二步：统计当前所有包裹里被大件腾出来的"2*2 槽位"总数。
        // 5*5 旁边只能放 1*1；4*4 旁边能放 5 个 2*2；
        // 3*3 按每箱剩余个数 0/1/2/3 分别能放 0/5/3/1 个 2*2。
        ll slots_two = 5 * cnt4 + left_for_two[cnt3 % 4];

        // 2*2 槽位不够就再开新箱，每箱最多 9 个 2*2
        if (cnt2 > slots_two) {
            boxes += (cnt2 - slots_two + 8) / 9;
        }

        // 第三步：剩下的空间全归 1*1。
        // 总面积减去已被占用的面积（6*6 用 36、5*5 用 25、4*4 用 16、3*3 用 9、2*2 用 4），
        // 就是所有包裹加起来还能放下的 1*1 个数。
        ll slots_one = 36 * boxes - 36 * cnt6 - 25 * cnt5 - 16 * cnt4 - 9 * cnt3 - 4 * cnt2;

        // 放不下 1*1 就继续开新箱，每箱 36 个
        if (cnt1 > slots_one) {
            boxes += (cnt1 - slots_one + 35) / 36;
        }

        cout << boxes << "\n";
    }

    return 0;
}

复杂度

时间：每个订单只做常数次整数运算（ $O(1)$ ），设订单数为 $T$ ，总时间 $O(T)$ 。真实数据里最大一档（boxes8）有 50 个订单、每个型号数量在 $3000$ 以内， C++ 与 Python 都在毫秒级完成，限时 1000 ms 绰绰有余。
空间：只保存当前订单的六个计数与累计箱数， $O(1)$ 。 C++ 的 left_for_two[4] 是唯一的常量表。

总结

高度相同的三维装箱退化成二维方格切割，这是本题的第一个关键观察；
由大到小逐层处理： $6/5/4$ 各占一箱 → $3$ 每四箱一个 → 查表补 $2 \times 2$ → 总面积补 $1 \times 1$ ，每层都取到硬下界，因此贪心正确；
唯一需要"记下来"的细节是 $3 \times 3$ 余数对应的 $2 \times 2$ 槽位数 $(k=0,1,2,3) \to (0,5,3,1)$ ，其余全部由公式直接给出；
两个坑： $1 \times 1$ 那一层要用更新后的 boxes 重算总面积；输入以六个 $0$ 结束，该行不输出。

目录

形式化题目

正解

思路

代码

复杂度

总结