题解：P16380 [NordicOI 2026] Catching Apples 接苹果

DrDuck · 2026-05-10 15:04:51 · 题解

打 ABC 遇到原题了（赛时去磕 F 了，没切）。

将所有苹果按出现时间升序排序，机器人能在接到苹果 i 之后接到苹果 j 等价于：

将绝对值拆开：

设苹果的两个属性 a_i = x_i - t_i,b_i = x_i + t_i，再将所有苹果按 a_i 升序排序，则相当于对于 b_i 求最长非严格下降子序列最小链划分。根据 Dilworth 定理，相当于求最长严格上升子序列长度。设 f_i 为以 b_i 为结尾的最长严格上升子序列长度，g_i 为所有长度为 i 的最长严格上升子序列长度的最小结尾，根据这个题的原理，使用二分优化，可以实现 O(n \log n)。

然后要我们输出方案。

结论：输出所有 f_i 即可。当然要按原序列顺序输出。

证明：这相当于对于所有结尾而言，最长严格上升子序列长度相同的用同一个机器人收集。那么必定有 b_i \ge b_j 满足，证明考虑反证法，假设 b_i < b_j，那么必定有 f_i < f_j，与 f_i = f_j 矛盾。所以是合法的。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e+5 + 5, inf = 1e17;
int n;
int f[maxn], g[maxn], pre[maxn], czs[maxn];
struct V {
    int t, x, id;
    friend bool operator < (const V &x, const V &y) {
        if (x.t == y.t) return x.x > y.x;
        return x.t < y.t;
    }
}a[maxn], b[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].x;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) b[i] = {a[i].x - a[i].t, a[i].x + a[i].t, a[i].id};
    sort(b + 1, b + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        g[i] = inf;
        int l = 1, r = i - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (g[mid] < b[i].x) {
                f[i] = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        f[i]++;
        ans = max(ans, f[i]);
        g[f[i]] = min(g[f[i]], b[i].x);
        czs[b[i].id] = f[i];
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) cout << czs[i] << ' ';
    return 0;
}

:::