AT_joi2023ho_b.宣伝 2 (Advertisement 2)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```
4
4 2
2 3
3 4
6 5
```
输出#1
```
2
```
输入#2
```
3
7 10
10 10
7 10
```
输出#2
```
2
```

输入#3

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

输出#3

说明/提示

小题

（ $10$ 分） $E_1 = E_2 = \cdots = E_N$ 。
（ $23$ 分） $N \leq 16$ 。
（ $36$ 分） $N \leq 1\,000$ 。
（ $31$ 分）没有额外约束。

样例解释1

例如如下赠书方案，可以使得 JOI 国所有居民都获得理恵的书。

向居民 $3$ $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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页