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 翻译