AT_joi2023ho_b 宣伝 2 (Advertisement 2)

JOI 国有 $N$ 名居民，编号从 $1$ 到 $N$。居民 $i$（$1 \leq i \leq N$）居住在数轴上的坐标 $X_i$，其“影响力”为 $E_i$。可能有多个居民居住在同一坐标。影响力越高的居民，宣传效果越大，但购书时会更加谨慎。 理恵出版了一本信息科学的书。为了让更多的人购买她的书，她可以向若干居民赠书。如果向居民 $i$（$1 \leq i \leq N$）赠书，则居民 $i$ 会得到理恵的书。此外，对于尚未拥有理恵的书的所有居民 $j$（$1 \leq j \leq N$），如果满足以下条件，则也会购买并获得理恵的书： - 居民 $i$ 与居民 $j$ 在数轴上的距离不超过 $E_i-E_j$，即 $|X_i-X_j| \leq E_i-E_j$。 如果 JOI 国的所有居民都能读到理恵的书，信息奥林匹克的知名度将会极大提升。请编写程序，求出最少需要赠书给几位居民，才能使 JOI 国所有居民都获得理恵的书。

输入以如下格式从标准输入读入： > $N$ > $X_1\ E_1$ > $X_2\ E_2$ > $\vdots$ > $X_N\ E_N$

输出一个整数，表示理恵最少需要赠书的居民人数。

## 小题 1. （$10$ 分）$E_1 = E_2 = \cdots = E_N$。 2. （$23$ 分）$N \leq 16$。 3. （$36$ 分）$N \leq 1\,000$。 4. （$31$ 分）没有额外约束。 --- ## 样例解释1 例如如下赠书方案，可以使得 JOI 国所有居民都获得理恵的书。 - 向居民 $3$ 赠书。 - $|X_3 - X_1| = 1, E_3 - E_1 = 2$，因此居民 $1$ 会购书获得理恵的书。 - $|X_3 - X_2| = 1, E_3 - E_2 = 1$，因此居民 $2$ 会购书获得理恵的书。 - $|X_3 - X_4| = 3, E_3 - E_4 = -1$，因此居民 $4$ 不会购书。 - 所以，居民 $1,2,3$ 都获得了理恵的书。 - 向居民 $4$ 赠书。此时其余居民都已经获得书，因此全部居民都获得了理恵的书。 少于 $2$ 人赠书不能使所有人都获得理恵的书，所以输出 $2$。 该输入样例满足小题 $2,3,4$ 的约束。 --- ## 样例解释2 此例输入输出满足所有小题的约束。 --- ## 样例解释3 此输入满足小题 $2,3,4$ 的约束。 # 数据范围 - $1 \leq N \leq 500\,000$。 - $1 \leq X_i \leq 10^9$ （$1 \leq i \leq N$）。 - $1 \leq E_i \leq 10^9$ （$1 \leq i \leq N$）。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译