题目大意

有 $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$ 均不降。

最小链覆盖与 Dilworth 定理

在偏序集（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)$：

• 在已有的车中，找一辆最后 $B$ 值小于等于当前 $B$ 的车，并且选最后 $B$ 值最大的那一辆。
• 如果找到，就把该糖果分配给这辆车，并更新该车的最后 $B$ 值为当前 $B$。
• 如果找不到，就新增一辆收集车，并设置其最后 $B$ 为当前 $B$。

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

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

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