AT_abc434_e.[ABC434E] Distribute Bunnies

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

有 $N$ 只编号为 $1$ 到 $N$ 的兔子站在数轴上。第 $i$ 只兔子站在坐标 $X_i$ 处，多个兔子可能站在同一个坐标上。
每只兔子有一个称为“跳跃力”的参数，第 $i$ 只兔子的跳跃力为 $R_i$ 。
现在，所有兔子各跳一次。当一只位于坐标 $x$ ，跳跃力为 $r$ 的兔子跳跃时，它可以跳到 $x+r$ 或 $x-r$ 的位置。
如果你可以自由选择每只兔子跳到哪个坐标，问所有兔子跳完后，最多能有多少个不同的坐标上有兔子。

输入格式

输入从标准输入读入，格式如下：

$N$
$X_1$ $R_1$
$X_2$ $R_2$
$\vdots$
$X_N$ $R_N$

输出格式

输出一个整数，表示所有兔子跳跃后，最多可能有多少个不同的坐标上有兔子。

输入输出样例

输入#1
```
3
4 1
2 3
4 5
```
输出#1
```
3
```
输入#2
```
6
2 1
3 2
6 1
5 2
4 3
4 1
```
输出#2
```
4
```

输入#3

10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3

输出#3

说明/提示

样例解释 1

如果每只兔子的跳跃方式如下，可以获得最大不同坐标数 $3$ 。

兔子 1 跳到 $4 - 1 = 3$ 。
兔子 2 跳到 $2 + 3 = 5$ 。
兔子 3 跳到 $4 - 5 = -1$ 。

样例解释 2

如果每只兔子的跳跃方式如下，可以获得最大不同坐标数 $4$ 。

兔子 1 跳到 $2 - 1 = 1$ 。
兔子 2 跳到 $3 + 2 = 5$ 。
兔子 3 跳到 $6 + 1 = 7$ 。
兔子 4 跳到 $5 + 2 = 7$ 。
兔子 5 跳到 $4 - 3 = 1$ 。
兔子 6 跳到 $4 - 1 = 3$ 。

数据范围

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq X_i \leq 10^9$
$1 \leq R_i \leq 10^9$
所有输入均为整数。

由 ChatGPT 5 翻译

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

首页