20260827B 街机游戏笔记

考虑一只手可以同时操作的 $i, j$ ，假设 $T_{i} \leq T_{j}$ ，则有

T_{j} - T_{i} \geq | A_{i} - A_{j} |

拆开绝对值

T_{j} - T_{i} \geq A_{i} - A_{j} \Rightarrow T_{i} + A_{i} \leq T_{j} + A_{j} (A_{i} \leq A_{j})

T_{j} - T_{i} \geq A_{j} - A_{i} \Rightarrow T_{i} - A_{i} \leq T_{j} - A_{j} (A_{i} > A_{j})

恰好，当 $A_{i} \leq A_{j}$ 时，下面一条一定成立，反之亦然，因此可以视作 $(T_{i} + A_{i}, T_{i} - A_{i})$ 的二维偏序最小覆盖问题。

运用 Dilworth 定理即可做到 $O (n \log n)$ 。

20260827B 街机游戏 笔记 ​