社区讨论

提供中文题面

aazky2024
AT_abc434_e[ABC434E] Distribute Bunnies参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mio6xva8
此快照首次捕获于
2025/12/02 14:22
3 个月前
此快照最后确认于
2025/12/04 10:05
3 个月前
查看原帖
rt。

[ABC434E] Distribute Bunnies

题目描述

在数轴上有编号为 11 到 NN 的 NN 只兔子。兔子 ii 在坐标 XiX_i 。多个兔子可能在同一坐标。
每只兔子有一个参数叫跳跃能量，兔子 ii 的跳跃能量 RiR_i 。
现在，所有的兔子都只跳一次。当位于坐标 xx 且具有跳跃能力 rr 的兔子跳跃时，它可以移动到坐标 x+rx+r 或坐标 x−rx-r 。
如果你可以自由选择每只兔子跳跃到的坐标，使兔子跳跃后兔子所在的不同坐标数量最大化，输出这个最大化后的值。

输入格式

第一行一个正整数 NN （ N≤2×105N \leq 2 \times 10^5 ）。
接下来 NN 行，第 ii 行有两个数字 XiX_i 和 RiR_i （ −109≤Xi≤109-10^9 \leq X_i \leq 10^9 ， 1≤Ri≤1091 \leq R_i \leq 10^9 ）。

输出格式

输出兔子跳跃后所在的不同坐标数量最大化后的值。

输入输出样例 #1

输入 #1

CPP
3
4 1
2 3
4 5

输出 #1

CPP
3

输入输出样例 #2

输入 #2

CPP
6
2 1
3 2
6 1
5 2
4 3
4 1

输出 #2

CPP
4

输入输出样例 #3

输入 #3

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

输出 #3

CPP
9

说明/提示

样例解释 #1

如果每只兔子都按如下方式移动，那么兔子跳跃后出现的不同坐标数 33 就是最大值。
  • 兔子 11 移动到 4−1=34 - 1 = 3 。
  • 兔子 22 移动到 2+3=52 + 3 = 5 。
  • 兔子 33 移动到 4−5=−14 - 5 = -1 。

样例解释 #2

如果每只兔子都按如下方式移动，那么兔子跳跃后出现的不同坐标数 44 就是最大值。
  • 兔子 11 移动到 2−1=12 - 1 = 1 。
  • 兔子 22 移动到 3+2=53 + 2 = 5 。
  • 兔子 33 移至 6+1=76 + 1 = 7 。
  • 兔子 44 移至 5+2=75 + 2 = 7 。
  • 兔子 55 移至 4−3=14 - 3 = 1 。
  • 兔子 66 移至 4−1=34 - 1 = 3 。

回复

共 4 条回复，欢迎继续交流。

正在加载回复...