AT_abc457_g [ABC457G] Catch All Apples

题目描述

有 $N$ 个苹果掉落在数轴上。第 $i$ 个苹果在时刻 $T_i$ 掉落在坐标 $X_i$。 你可以在数轴上任意位置放置若干机器人,用来收集这 $N$ 个苹果。每个机器人可以放在任意坐标上,从时刻 $0$ 开始工作,可以在数轴上自由移动,最大速度为 $1$。多个机器人可以在同一时刻占据同一坐标。机器人只有在时刻 $T_i$ 到达坐标 $X_i$ 时,才能收集第 $i$ 个苹果。 请你求出收集所有苹果所需的最少机器人数量。

输入格式

输入以标准输入方式给出,格式如下: > $N$ > $T_1$ $X_1$ > $T_2$ $X_2$ > $\vdots$ > $T_N$ $X_N$

输出格式

输出一个整数,表示需要的最少机器人数量。

说明/提示

### 样例解释 1 所有苹果可以用两个机器人按如下方式收集: - 将机器人 1 放在坐标 $0$,机器人 2 放在坐标 $2$。 - 时刻 $0$:机器人 2 在坐标 $2$ 收集苹果 1。 - 时刻 $1$:机器人 1 在坐标 $1$ 收集苹果 2。两只机器人都以速度 $1$ 向正方向移动,直到时刻 $2$。 - 时刻 $2$:机器人 1 在坐标 $2$ 收集苹果 3,机器人 2 在坐标 $4$ 收集苹果 4。 无法用少于两台机器人收集所有苹果,因此输出 $2$。 ### 约束条件 - $1 \le N \le 3 \times 10^5$ - $0 \le T_i \le 3 \times 10^5$ - $0 \le X_i \le 3 \times 10^5$ - $(T_i, X_i) \neq (T_j, X_j)$ 且 $i \neq j$ - 所有输入值均为整数。 由 ChatGPT 5 翻译