P3120 - 气球 - 创客家题库

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：0 解决：0

在一个二维坐标系上，悬浮着 $n$ 只静止不动的气球，第 $i$ 个气球的坐标为 $(x_{i}, h_{i})$ ， $x_{i}$ 表示它的横坐标， $h_{i}$ 表示它的高度。保证在同一个坐标上，最多只有一只气球。

小爱打算用最少的弓箭射穿所有的气球，每只弓箭射出时，需要确定一个高度，当弓箭没有遇到气球时，它会一直保持同样的高度沿 $x$ 轴正方向运动，如果弓箭碰到了气球，气球就会被射穿，弓箭的高度会减少 $1$ ，然后继续沿水平方向运动，直到遇到下一个气球。

请问，小爱最少需要射出多少只箭，才能将所有的气球全部射穿?

第一行：单个正整数表示

n

。
接下来

n

行，每行两个整数，表示一只气球的坐标。

对于 $30 %$ 的数据， $1 \leq n \leq 1 0^{3}$ ；
对于 $60 %$ 的数据， $1 \leq n \leq 1 0^{4}$ ；
对于 $100 %$ 的数据， $1 \leq n \leq 1 0^{5}$ ， $1 \leq x_{i} \leq n$ ， $1 \leq h_{i} \leq 2 n$ 。

单个正整数，表示最少需要多少只箭才能拿射穿所有的气球。

第一支箭的射穿高度为2,1的气球，第二支箭的射穿高度为5,4,3的气球
每一只箭只能射穿一只气球

5
4 1
1 4
2 5
3 2
5 4

3

提交提交记录统计露一手!

3120: 气球