← 返回题目列表

AtCoder · abc457_g

G. 抓住所有苹果

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

N 苹果落在数轴上。苹果 i 落在坐标处 X_i 时间 T_i.

你想在数轴上放置一些机器人来收集所有 N 苹果。机器人可以放置在任意坐标。

每个机器人从时间开始运行 0 并且可以沿数轴自由移动,速度最多为 1。多个机器人可以同时占据同一坐标。每个机器人都可以收集苹果 i 当且仅当它位于坐标处 X_i 时间 T_i.

找出收集所有苹果所需的最少机器人数量。

约束

  • 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)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
T_1 X_1
T_2 X_2
\vdots
T_N X_N

输出

输出答案。


示例输入 1

4
0 2
1 0
2 1
2 3

示例输出 1

2

所有苹果都可以通过两个机器人通过移动来收集,如下所示:

  • 放置机器人 1 位于坐标处 0 和机器人 2 位于坐标处 2.
  • 时间 0:机器人 2 收集苹果 1.
  • 时间 1:机器人 1 收集苹果 2。使两个机器人快速向正方向移动 1 直到时间 2.
  • 时间 2:机器人 1 收集苹果 3 和机器人 2 收集苹果 4.

少于两个机器人不可能收集到所有苹果,因此输出 2.


示例输入 2

5
0 1
0 2
0 3
0 4
0 5

示例输出 2

5

示例输入 3

8
10 4
4 2
7 10
5 3
1 9
0 6
3 8
0 9

示例输出 3

2