题目解释

给定 $N$ 个苹果，每个苹果在时间 $t_i$ 出现在位置 $x_i$。机器人速度 $\le1$，问最少需要多少个机器人才能接到所有苹果，并输出每个苹果由哪个机器人接。

解法：Dilworth 定理 + 最长递增子序列 LIS

关键公式

如果两个苹果 $i$ 和 $j$ 可以被同一个机器人借助，则当且仅当：

$$|x_j - x_i| \le t_j - t_i$$

将绝对值展开可得：

$$x_j - t_j \le x_i - t_i \\ x_j + t_j \ge x_i + t_i$$

这时候我们定义：

$$a_i = x_i - t_i,\quad b_i = x_i + t_i$$

于是苹果 $i，j$ 可被同一个机器人接住的条件可化简为：

$$a_j \le a_i \quad \land \quad b_j \ge b_i$$

此时这道题被转化为了偏序集问题（Dilworth 定理）：

将所有苹果按如下规则排序：

先按 $b_i$ 升序；

若 $b_i$ 相等，按 $a_i$ 降序排列。

排序之后问题被再次转化：

同一个机器人承接的苹果对应序列中一个非递增子序列；两两不能同机器人的苹果构成严格递增子序列（反链）。

这时候进行最后一步转化就可以得出答案了：

根据 Dilworth 定理，有限偏序集上： 最少链划分数量 $=$ 最长反链长度。

在这道题上可以体现为：最少机器人个数 $=$ 序列 $a_i$ 的最长严格递增子序列 LIS 长度。

同时在求解 LIS 过程中，可以给每个苹果分配机器人编号。

到这里这道问题就被解决了，更细节的内容会在代码里解释。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200005;
int n, dp[MAXN], ans[MAXN], chain[MAXN];
struct dmh {
    int a, b, id;
} q[MAXN];

bool cmp(dmh a, dmh b) {
    if (a.b == b.b) return a.a > b.a;/b是第一关键字。
    return a.b < b.b;
}

signed main() {
    scanf("%lld", &n);
    int t, x;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &t, &x);
        q[i].a = x - t;//通过推倒得到的公式。
        q[i].b = x + t;
        q[i].id = i;//记录苹果的编号。
    }
    sort(q + 1, q + 1 + n, cmp);//对苹果进行排序。
    int cnt = 0;
    dp[0] = -2e9;
    for (int i = 1; i <= n; i++) {//计算严格递增子序列LIS的长度。
        int val = q[i].a;
        if (val > dp[cnt]) {
            dp[++cnt] = val;
            chain[i] = cnt;
        } else {
            int l = 1, r = cnt;
            while (l < r) {//二分优化。
                int mid = (l + r) >> 1;
                if (dp[mid] >= val) r = mid;
                else l = mid + 1;
            }
            dp[l] = val;
            chain[i] = l;
        }
        ans[q[i].id] = chain[i];//记录每个苹果被哪个机器人采摘。
    }
    printf("%lld\n", cnt);
    for (int i = 1; i <= n; i++) {
        printf("%lld ", ans[i]);
    }
    return 0;
}

补充说明：如果不太明白 LIS 的原理可以移步 P1020 学习。