题解：P11546 [BalticOI 2009] 糖果机器 (Day1)

AT_doming_Cl2 · 2026-04-25 17:14:40 · 题解

题目大意

有 n 颗糖果，第 i 颗会在时刻 t_i 从槽 s_i 掉出。一辆收集车每秒可以移动到相邻的槽，并且在生产开始前可以预先停在任意位置。你需要用最少的收集车接住所有糖果（不能掉落）。要求输出最少车辆数，并给出每颗糖果对应的车辆编号。

前轱辘不转后轱辘转，那题目本身看不懂，就先转换为数学式子呗。

设一辆收集车依次接住了糖果 i 和糖果 j（i 先于 j）。由于车速为每秒 1 格，从槽 s_i 移动到 s_j 至少需要 |s_j - s_i| 秒，因此必须满足：

t_j - t_i \ge |s_j - s_i|

把恶心的绝对值拆开：

\begin{cases} t_j + s_j \ge t_i + s_i \\ t_j - s_j \ge t_i - s_i \end{cases}

定义每个糖果的两个特征值：

A_i = t_i + s_i, \quad B_i = t_i - s_i

那么一辆收集车可以先后接住 i 和 j（i 在前）当且仅当 A_i \le A_j 且 B_i \le B_j。

换句话说，如果将糖果按照被同一辆车接住的顺序排成一个序列，这个序列在 A 和 B 上都是不降的。

因此问题转化为：

平面上有 n 个点 (A_i, B_i)，要用最少的不降链覆盖所有点。这里“不降链”指序列中 A、B 均不降。

在偏序集（poset）中，链是一个两两可比较的元素序列，反链是一个两两不可比较的集合。对于本题，定义偏序关系：

i \preceq j \iff A_i \le A_j \land B_i \le B_j

链就是可以被同一辆车依次接住的糖果序列，反链就是任意两个糖果都不能被同一辆车接住（即必须用不同车辆）。

Dilworth 定理指出：有限偏序集的最小链覆盖数等于最长反链的长度。

因此，最少收集车数量 = 最长反链大小。

这里的最长反链，等价于从点集中选出尽可能多的点，使得它们两两不可比较。这正好可以用二维偏序的经典方法求出，例如对第一维排序后求第二维的最长下降子序列（因为不可比较意味着 A_i < A_j 时必须有 B_i > B_j，反之亦然）。

However，本题还需要输出具体每颗糖果由哪辆车接住，也就是要求出链覆盖方案。我们可以用贪心构造的方法直接得到方案，同时自然得到最小链数（车辆数）。

将所有糖果按照 A 从小到大的顺序处理，A 相同时按 B 从小到大，这样保证前面的棋子不会在 A 上超过后面的。

维护当前每辆收集车最后接住的糖果的 B 值（以及车辆编号）。对于当前糖果 (A, B)：

这个贪心过程和经典的“导弹拦截”第二问完全一致，正确性可由 Dilworth 定理及贪心性质保证。算法结束时，使用的车辆数就等于最长反链长度，也就是最小链覆盖数。

使用 set 维护所有 (last_B, machine_id) 对，每次在 set 中二分查找最后一个 \le B 的元素，时间复杂度 O(n \log n)，可以处理 10^5 的数据规模。

::::info[AI 使用情况披露] 本题解使用了 DeepSeek 进行润色。 ::::