P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2

JOI 王国有 $N$ 位居民，编号从 $1$ 到 $N$。居民 $i$ ($1 \le i \le N$) 住在实数轴上的坐标 $X_i$ 处，其**影响力**为 $E_i$。可能有多个居民住在同一坐标处。拥有较大影响力的居民具有较高的广告潜力，但这样的居民在购买书籍时很谨慎。 Rie 出版了一本信息学的书。为了鼓励更多人购买这本书，她可以向一些居民赠送这本书的副本。如果她向居民 $i$ ($1 \le i \le N$) 赠送了一本书，居民 $i$ 将获得 Rie 的书。此外，在尚未获得书的居民中，满足以下条件的每位居民 $j$ ($1 \le j \le N$) 都会购买一本书并获得它。 - 居民 $i$ 和居民 $j$ 在实数轴上的距离小于或等于 $E_i - E_j$。换句话说，满足 $|X_i - X_j| \le E_i - E_j$。 如果所有居民都阅读了 Rie 的书，信息学奥林匹克将得到极大的认可。编写一个程序，计算需要向多少位居民赠送 Rie 的书，才能使 JOI 王国的所有居民都获得 Rie 的书。

从标准输入读取以下数据。 > $N$ > $X_1$ $E_1$ > $X_2$ $E_2$ > $\vdots$ > $X_N$ $E_N$

向标准输出写入一行。输出应包含需要赠送 Rie 的书的最少居民数量，以便 JOI 王国的所有居民都获得 Rie 的书。

## 样例 ### 样例 1 例如，如果 Rie 按以下方式赠送书，JOI 王国的所有居民将获得 Rie 的书。 - Rie 向居民 3 赠送了一本书。 - 因为 $|X_3 - X_1| = 1$ 且 $E_3 - E_1 = 2$，居民 1 会购买一本 Rie 的书并获得它。 - 因为 $|X_3 - X_2| = 1$ 且 $E_3 - E_2 = 1$，居民 2 会购买一本 Rie 的书并获得它。 - 因为 $|X_3 - X_4| = 3$ 且 $E_3 - E_4 = -1$，居民 4 不会购买 Rie 的书。 因此，居民 1、2、3 将获得 Rie 的书。 - Rie 向居民 4 赠送了一本书。由于除了居民 4 之外的所有居民都已经获得了 Rie 的书，最终 JOI 王国的所有居民都获得了 Rie 的书。 由于不可能向少于两位居民赠送书以使 JOI 王国的所有居民都获得 Rie 的书，因此输出 2。 此样例输入满足子任务 2、3、4 的约束。 ### 样例 2 此样例输入满足所有子任务的约束。 ### 样例 3 此样例输入满足子任务 2、3、4 的约束。 ## 约束 - $1 \le N \le 5 \times 10^5$。 - $1 \le X_i \le 10^9$ ($1 \le i \le N$)。 - $1 \le E_i \le 10^9$ ($1 \le i \le N$)。 - 给定值均为整数。 ## 子任务 1. (10 分) $E_1=E_2=\cdots=E_N$。 2. (23 分) $N \le 16$。 3. (36 分) $N \le 10^3$。 4. (31 分) 无额外约束。 题面翻译由 ChatGPT-4o 提供。