核心思路

贪心匹配 + 剩余空间优化管理

重要公式与条件

1. 可行性必要条件

总物质体积不超过容器总容量：

2. 问题转化

将 $n$ 种物质分配到 $n$ 个容量为 $k$ 的容器中，每个容器最多装 2 种物质。

3. 关键观察

观察 1：大物质分割策略

• 对于 $a_i > k$ 的物质，必须分割到多个容器
• 最优策略是用大物质填充其他容器的剩余空间

观察 2：小物质利用策略

• 对于 $a_i \leq k$ 的物质，优先单独装箱
• 如果 $a_i < k$，产生的剩余空间用于容纳大物质的片段

观察 3：匹配优先级

• 最大剩余空间匹配最大剩余物质
• 保证空间利用率最大化

贪心算法框架

阶段 1：小物质处理

对于所有 $a_i \leq k$ 的物质：

• 分配新容器单独装载
• 记录产生的剩余空间 $r = k - a_i$

阶段 2：大物质处理

对于所有 $a_i > k$ 的物质：

• 从剩余空间集合中选取最大的 $r_{\max}$
• 填充量 $\Delta = \min(a_i, r_{\max})$
• 更新物质剩余量 $a_i \leftarrow a_i - \Delta$
• 更新容器剩余空间 $r_{\max} \leftarrow r_{\max} - \Delta$

阶段 3：循环处理

重复阶段 2 直到所有物质分配完毕

算法正确性分析

可行性保证

• 初始可行性检查确保问题有解
• 每次匹配都满足容器容量约束
• 物质分割满足任意分割的条件

最优性保证

• 优先处理小物质产生更多剩余空间
• 最大剩余空间匹配最大物质避免空间碎片
• 每个容器最多 2 种物质的约束自然满足

复杂度分析

• 使用平衡树维护物质和剩余空间：$O(n \log n)$
• 每个物质最多被处理 $O(1)$ 次
• 总操作次数 $O(n)$

特殊情况处理

情况 1：所有物质都很小

$(\forall i) a_i \leq k$

• 直接每个物质单独装箱
• 可能产生多个部分装满的容器

情况 2：存在超大物质

$(\exists i) a_i \gg k$

• 该物质会被分割到多个容器
• 利用其他容器产生的剩余空间

情况 3：物质总量刚好等于总容量

$\sum a_i = n \cdot k$

• 所有容器必须完全装满
• 需要精确的匹配和分割