A6978. 连锁反应
编程题
普及/提高-
知识点
题目描述
在数轴上有 $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$