310521: CF1846A. Rudolph and Cut the Rope
Description
There are $n$ nails driven into the wall, the $i$-th nail is driven $a_i$ meters above the ground, one end of the $b_i$ meters long rope is tied to it. All nails hang at different heights one above the other. One candy is tied to all ropes at once. Candy is tied to end of a rope that is not tied to a nail.
To take the candy, you need to lower it to the ground. To do this, Rudolph can cut some ropes, one at a time. Help Rudolph find the minimum number of ropes that must be cut to get the candy.
The figure shows an example of the first test:
The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains one integer $n$ ($1 \le n \le 50$) — the number of nails.
The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 200$) — the height of the $i$-th nail and the length of the rope tied to it, all $a_i$ are different.
It is guaranteed that the data is not contradictory, it is possible to build a configuration described in the statement.
OutputFor each test case print one integer — the minimum number of ropes that need to be cut to make the candy fall to the ground.
ExampleInput4 3 4 3 3 1 1 2 4 9 2 5 2 7 7 3 4 5 11 7 5 10 12 9 3 2 1 5 3 5 6 4 5 7 7Output
2 2 3 0
Input
题意翻译
#### 题目大意 现在有 $n$ 个钉子被钉在墙上，第 $i$ 个钉子离地 $a_i$ 米。每个钉子都被一根长度为 $b_i$ 绳子的一端所连接。所有钉子一个接一个地被钉在不同的高度。一个糖果被一次性系在所有的绳子上，它被系在绳子不与钉子相连的那一端。 为了拿到那颗糖果，你需要将他放到地面上。为了做这件事， $Rudolph$ 可以一次一条地剪断一些绳子。帮助 $Rudolph$ 找到获得糖果需要剪断的绳子数量的最小值。 以下图像展示的是第一组样例。 #### 输入格式 第一行包括一个数字 $t~(1 \le t \le 10^4)$ —— 测试用例的数量 每个测试用例的第一行为一个数字 $n ~(1 \le n \le 50)$ —— 钉子的数量 接下来 $n$ 中的第 $i$ 行每行包含两个数字 $a_i$ 和 $b_i$ $(1 \le a_i,b_i \le 200)$ —— 第 $i$个钉子的高度和连接在它上面的绳子长度，每个 $a_i$ 是不同的。 保证所有数据都不会相互矛盾，并且可以构建题目中所描述的构造， #### 输出格式 对每个测试样例输出一个数字 —— 让糖果落到地面所需要剪断的绳子数量的最小值。Output
鲁道夫需要帮助将挂在多个不同高度的钉子上的绳子绑着的糖果降到地面。每次他可以切割一根绳子。请帮助鲁道夫找到需要切割的最少的绳子数量，以便让糖果落到地面。
输入数据格式：
第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)），表示测试用例的数量。
每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 50 \)），表示钉子的数量。
接下来 \( n \) 行，每行包含两个整数 \( a_i \) 和 \( b_i \)（\( 1 \le a_i, b_i \le 200 \)），分别表示第 \( i \) 个钉子距离地面的高度和绑在上面的绳子的长度。所有 \( a_i \) 的值都是不同的。
保证数据没有矛盾，可以构建出题目描述中的配置。
输出数据格式：
对于每个测试用例，输出一个整数，表示为了让糖果落到地面，需要切割的最少绳子数量。
示例：
输入：
```
4
3
4 3
3 1
1 2
4
9 2
5 2
7 7
3 4
5
11 7
5 10
12 9
3 2
1 5
3
5 6
4 5
7 7
```
输出：
```
2
2
3
0
```题目大意： 鲁道夫需要帮助将挂在多个不同高度的钉子上的绳子绑着的糖果降到地面。每次他可以切割一根绳子。请帮助鲁道夫找到需要切割的最少的绳子数量，以便让糖果落到地面。 输入数据格式： 第一行包含一个整数 \( t \)（\( 1 \le t \le 10^4 \)），表示测试用例的数量。 每个测试用例的第一行包含一个整数 \( n \)（\( 1 \le n \le 50 \)），表示钉子的数量。 接下来 \( n \) 行，每行包含两个整数 \( a_i \) 和 \( b_i \)（\( 1 \le a_i, b_i \le 200 \)），分别表示第 \( i \) 个钉子距离地面的高度和绑在上面的绳子的长度。所有 \( a_i \) 的值都是不同的。 保证数据没有矛盾，可以构建出题目描述中的配置。 输出数据格式： 对于每个测试用例，输出一个整数，表示为了让糖果落到地面，需要切割的最少绳子数量。 示例： 输入： ``` 4 3 4 3 3 1 1 2 4 9 2 5 2 7 7 3 4 5 11 7 5 10 12 9 3 2 1 5 3 5 6 4 5 7 7 ``` 输出： ``` 2 2 3 0 ```