非遗巡展装箱：展品运输箱数量最少化

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：8
• 训练题主题：非遗巡展装箱：展品运输箱数量最少化
• 所属赛道：非遗文化赛道

题目背景

非遗巡展准备把展品统一装箱运输。每个箱子最多放两件展品，且总重量不能超过承重上限。为了减少运输次数，需要找出最少箱数，并统计其中单件装箱的数量与最大配对重量。

任务描述

• 读取所有展品重量和运输箱承重上限。
• 在每箱最多放两件的前提下，求最少运输箱数。
• 统计单件装箱数和配对装箱中的最大总重量。

输入格式

1. 第一行输入 n limit。
2. 第二行输入 n 个整数 w1..wn，表示每件展品重量。

输出格式

1. 第一行输出 boxes=最少运输箱数。
2. 第二行输出 single_boxes=单件装箱数。
3. 第三行输出 max_pair=成对装箱中的最大总重量，若无配对则输出 0。

数据范围与说明

• 1 <= n <= 2 * 10^5。
• 1 <= wi <= limit <= 10^9。
• 每个运输箱最多装 2 件。
• 若最轻与最重能同箱，则必须优先尝试配对。

样例输入

6 10
2 3 5 6 7 8

样例输出

boxes=4
single_boxes=2
max_pair=10

样例解释

• 排序后可配成 (2,8) 和 (3,7) 两箱，5 与 6 只能单独装箱。
• 因此最少箱数是 4，其中单件装箱有 2 箱。
• 两次成功配对的总重量最大值为 10。

知识点清单

• 排序后的双指针收缩。
• 最轻件与最重件的贪心配对。
• 单件装箱与配对装箱统计。
• 边界情形 left == right 的处理。
• 最优装箱数量的构造思路。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 2 * 10^5。
• 1 <= wi <= limit <= 10^9。
• 每个运输箱最多装 2 件。
• 若最轻与最重能同箱，则必须优先尝试配对。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 排序 + 双指针贪心 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 只剩下一件展品时，必须单独装箱。
• 所有展品都可配对和所有展品都不可配对两种极端都要正确处理。
• 没有任何配对成功时，max_pair 要输出 0。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：optimization
• 主算法：排序 + 双指针贪心

判题重点

• 重点校验建模是否正确、最优值维护是否稳定、路径或方案恢复是否完整。
• 隐藏数据会覆盖不可达、同值竞争和多约束并存情形。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备所有展品重量都相同的样例，检查配对边界。
• 准备只有一件展品和只有两件展品的极小数据。
• 准备总有一侧无法配对的升序数据，验证单件统计。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

6 10
2 3 5 6 7 8

样例输出：sample.out

boxes=4
single_boxes=2
max_pair=10

题解、建模与最终解法

自动整理的解题流程

• 题目主题：非遗巡展装箱：展品运输箱数量最少化
• 题目摘要：对展品重量排序后使用双指针贪心，求出最少运输箱数和单件箱数。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

对展品重量排序后使用双指针贪心，求出最少运输箱数和单件箱数。

2. 数据结构与建模

• 主算法：排序 + 双指针贪心
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 先对所有展品重量升序排序。
2. 用左右双指针分别指向当前最轻和最重的展品。
3. 若两者和不超过上限，就配成一箱；否则最重展品单独装箱。
4. 持续收缩双指针并维护箱数、单件箱数和最大配对重量。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 只剩下一件展品时，必须单独装箱。
• 所有展品都可配对和所有展品都不可配对两种极端都要正确处理。
• 没有任何配对成功时，max_pair 要输出 0。

7. 知识点清单

• 排序后的双指针收缩。
• 最轻件与最重件的贪心配对。
• 单件装箱与配对装箱统计。
• 边界情形 left == right 的处理。
• 最优装箱数量的构造思路。

设计决策记录

源文件：decision-log.md

• 选择 排序 + 双指针贪心 作为主算法，因为它能直接覆盖题目的核心约束。
• 每箱最多两件且目标是最少箱数，是经典双指针贪心模型。
• 先配最轻和最重可以最大限度减少最重展品单独占箱的情况。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备所有展品重量都相同的样例，检查配对边界。
• 准备只有一件展品和只有两件展品的极小数据。
• 准备总有一侧无法配对的升序数据，验证单件统计。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    limit = next(it)
    weights = sorted(next(it) for _ in range(n))
    left = 0
    right = n - 1
    boxes = 0
    single_boxes = 0
    max_pair = 0
    while left <= right:
        boxes += 1
        if left == right:
            single_boxes += 1
            break
        if weights[left] + weights[right] <= limit:
            pair_weight = weights[left] + weights[right]
            if pair_weight > max_pair:
                max_pair = pair_weight
            left += 1
            right -= 1
        else:
            single_boxes += 1
            right -= 1
    return "\n".join(
        [
            f"boxes={boxes}",
            f"single_boxes={single_boxes}",
            f"max_pair={max_pair}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

代码执行与运行结果

最新成功运行

PY 运行输出摘录

boxes=4
single_boxes=2
max_pair=10

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s1-jh-08-heritage-transport-packing/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s1-jh-08-heritage-transport-packing/02-solution
• 运行证据：10-cases/s1-jh-08-heritage-transport-packing/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md

• 完整解题档案：complete-solution-dossier.md
• 代码附录：appendix-code.md
• 运行附录：appendix-runs.md

题目概述

对展品重量排序后使用双指针贪心，求出最少运输箱数和单件箱数。

最终解法摘要

自动整理的解题流程

• 题目主题：非遗巡展装箱：展品运输箱数量最少化
• 题目摘要：对展品重量排序后使用双指针贪心，求出最少运输箱数和单件箱数。
• 判题提示：该题以优化求解为主，重点是约束建模、可行性检查和最优值维护。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

代码执行摘要

交付说明

本报告为摘要版，详细题目、题干、题解、最终代码、运行结果和调试流程已经汇总到完整解题档案中。