A6978 | 连锁反应
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在数轴上有 $n$ 个位置不同的信标。第 $i$ 个信标位于位置 $a_i$，其能量等级为 $b_i$。
如果第 $i$ 个信标被激活，它将摧毁其左侧（坐标小于 $a_i$）所有距离在 $b_i$ 以内（包括 $b_i$）的信标。即坐标在 $[a_i - b_i, a_i - 1]$ 范围内的信标都会被摧毁。信标被激活后，自身不会被摧毁。
埼玉（Saitama）将从右向左依次激活这些信标。如果一个信标在轮到它被激活之前已经被摧毁，那么它将无法被激活，也就无法产生连锁反应。
为了尽可能减少被摧毁的信标数量，杰诺斯（Genos）计划在所有现有信标的右侧（坐标严格大于所有 $a_i$）添加一个新的信标。这个新信标的位置和能量等级可以是任意值。注意：由于新信标位于最右侧，它将是第一个被激活的信标。
请你帮助杰诺斯计算，通过合理放置这个新信标，最少会有多少个原有的信标被摧毁。
如果第 $i$ 个信标被激活，它将摧毁其左侧（坐标小于 $a_i$）所有距离在 $b_i$ 以内（包括 $b_i$）的信标。即坐标在 $[a_i - b_i, a_i - 1]$ 范围内的信标都会被摧毁。信标被激活后，自身不会被摧毁。
埼玉（Saitama）将从右向左依次激活这些信标。如果一个信标在轮到它被激活之前已经被摧毁，那么它将无法被激活，也就无法产生连锁反应。
为了尽可能减少被摧毁的信标数量，杰诺斯（Genos）计划在所有现有信标的右侧（坐标严格大于所有 $a_i$）添加一个新的信标。这个新信标的位置和能量等级可以是任意值。注意：由于新信标位于最右侧，它将是第一个被激活的信标。
请你帮助杰诺斯计算，通过合理放置这个新信标，最少会有多少个原有的信标被摧毁。
输入格式
第一行包含一个整数 $n$，表示初始信标的数量。
接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 个信标的位置和能量等级。
保证所有信标的位置 $a_i$ 互不相同。
接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 个信标的位置和能量等级。
保证所有信标的位置 $a_i$ 互不相同。
输出格式
输出一个整数，表示最少被摧毁的信标数量。
输入输出样例
输入 #1
4 1 9 3 1 6 1 7 4
输出 #1
1
输入 #2
7 1 1 2 1 3 1 4 1 5 1 6 1 7 1
输出 #2
3
【样例 1 解释】
原有的信标位置为 $1, 3, 6, 7$。
可以在位置 $9$ 放置一个能量为 $2$ 的信标。
1. 新信标激活，攻击范围 $[7, 8]$。位置 $7$ 的信标被摧毁。
2. 接下来轮到位置 $6$ 的信标激活（它是最右边存活的），攻击范围 $[5, 5]$。无信标被摧毁。
3. 接下来位置 $3$ 激活，攻击范围 $[2, 2]$。无信标被摧毁。
4. 接下来位置 $1$ 激活，无左侧信标。
总共只有位置 $7$ 的信标被摧毁，数量为 1。
【数据范围】
对于 $100\%$ 的数据，满足：
- $1 \le n \le 100\,000$
- $0 \le a_i \le 1\,000\,000$
- $1 \le b_i \le 1\,000\,000$
原有的信标位置为 $1, 3, 6, 7$。
可以在位置 $9$ 放置一个能量为 $2$ 的信标。
1. 新信标激活，攻击范围 $[7, 8]$。位置 $7$ 的信标被摧毁。
2. 接下来轮到位置 $6$ 的信标激活（它是最右边存活的），攻击范围 $[5, 5]$。无信标被摧毁。
3. 接下来位置 $3$ 激活，攻击范围 $[2, 2]$。无信标被摧毁。
4. 接下来位置 $1$ 激活，无左侧信标。
总共只有位置 $7$ 的信标被摧毁，数量为 1。
【数据范围】
对于 $100\%$ 的数据，满足：
- $1 \le n \le 100\,000$
- $0 \le a_i \le 1\,000\,000$
- $1 \le b_i \le 1\,000\,000$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？