AtCoder 🔵 ABC457G Catch All Apples

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC457G Catch All Apples

Problem Statement

題目簡述

有 $N$ 顆蘋果會在指定時間出現在數線上的指定位置。
每個人一開始可以在任意位置，之後每單位時間最多移動 $1$，若某人能在蘋果出現的時間位於該位置，就可以接住那顆蘋果。

請求出最少需要多少人，才能把所有蘋果都接住。

Constraints

約束條件

• $1 \le N \le 3 \times 10^5$
• $0 \le T_i, X_i \le 3 \times 10^5$
• 所有 $(T_i, X_i)$ 兩兩不同
• 輸入皆為整數

---

思路：座標轉換 + Dilworth 定理

把可達性條件寫成不等式

考慮兩顆蘋果，假設前者的時間和位置為 $(T_i, X_i)$，後者為 $(T_j, X_j)$ 且 $T_i \le T_j$。同一個機器人能不能先接住前者再接後者？

機器人速度上限為 $1$，所以唯一的要求是：兩者的時間差足以覆蓋位置差，也就是 $|X_j - X_i| \le T_j - T_i$。

展開絕對值得到兩條不等式：

$$\begin{cases} X_j - X_i \le T_j - T_i \\[4pt] X_i - X_j \le T_j - T_i \end{cases}$$

整理後分別得到：

$$T_i + X_i \le T_j + X_j,\quad T_i - X_i \le T_j - X_j$$

兩者必須同時成立。也就是說，定義兩個轉換值 $u = T + X$ 和 $v = T - X$，則可接續的充要條件就是 $u_i \le u_j$ 且 $v_i \le v_j$。

從最少人數到最大反鏈

每顆蘋果對應到 $u$-$v$ 平面上的一個點。若 $i$ 能接續到 $j$，表示它們可由同一個機器人處理。因此，一條合法的受理序列對應到平面上兩座標都不下降的一條點列（鏈）。

題目問最少需要幾條不下降鏈才能覆蓋所有點——這正是偏序集的最少鏈覆蓋問題。

做過 P1020 [NOIP 1999 提高组] 导弹拦截 的讀者可能對這個轉換不陌生：根據 Dilworth 定理：在有限偏序集中，最少鏈覆蓋數等於最大反鏈的大小。

這裡的反鏈是一組兩兩不可接續的蘋果——任取兩顆，都無法排進同一個機器人的受理順序中。換句話說，對反鏈中的任意兩點 $i, j$，不能同時滿足 $u_i \le u_j$ 且 $v_i \le v_j$（否則它們就是可接續的）。

刻畫反鏈：v 的嚴格下降子序列

反鏈的條件——任意兩點不能同時滿足 $u_i \le u_j$ 且 $v_i \le v_j$ 的條件，只涉及點在兩個維度上的相對大小，與它們在序列中的出現順序無關。因此，為了方便判斷，我們可以先按 $u$ 排序，這並不會改變任何一對點是否構成反鏈。

在排序後的序列上，對任意滿足 $i < j$ 的兩點，$u_{i} \le u_{j}$ 已由順序自動保證。若它們同屬一個反鏈，$v_{i} \le v_{j}$ 就不能成立。這迫使反鏈內部的第二座標必須遞減：$v_{i} > v_{j}$，即 $v$ 沿序列嚴格下降。

反過來看，凡 $v$ 嚴格下降的子序列，其中任兩點必不滿足 $v_{i} \le v_{j}$，因此不滿足可接續條件，確實是合法反鏈。

綜上，$v$ 的嚴格下降子序列與反鏈一一對應，最長者的長度即為最大反鏈大小。

Success

最大反鏈大小 = 按 $T+X$ 排序後，$T-X$ 的**最長嚴格下降子序列(LDS)**長度。
由 Dilworth 定理，最少鏈覆蓋數等於此值，即所需的最少人數。

複雜度分析

• 時間複雜度：$\mathcal{O}(N \log N)$
• 空間複雜度：$\mathcal{O}(N)$

類題

• P1020 [NOIP 1999 提高组] 导弹拦截
• P5939 [POI 1998 R3] 折线

---

Code

from bisect import bisect_left


def solve():
    n = int(input())

    points = []
    for i in range(n):
        t, x = map(int, input().split())
        points.append((t + x, t - x))
    points.sort()

    # 求 v 的 LDS 長度
    f = []
    for _, v in points:
        idx = bisect_left(f, -v)
        if idx == len(f):
            f.append(-v)
        else:
            f[idx] = -v
    print(len(f))


if __name__ == "__main__":
    solve()