问题
  • 板块灌水区
  • 楼主sunhang601602
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/7 23:45
  • 上次更新2023/11/5 11:38:12
查看原帖
问题
348080
sunhang601602楼主2020/10/7 23:45

在一个二维坐标系上,悬浮着 n 只静止不动的气球,第 i 个气球的坐标为(xi,hi),xi 表示它的横坐标,

hi 表示它的高度。保证在同一个坐标上,最多只有一只气球。

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

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

【输入格式】输入文件 balloon.in 第一行:单个正整数表示 n。 接下来 n 行,每行两个整数,表示一只气球的坐标。

【输出格式】输出文件 balloon.out 单个正整数,表示最少需要多少只箭才能拿射穿所有的气球。

【输入输出样例 1】

5

1 2

3 5

4 4

5 3

2 1

2

说明:第一支箭的射穿高度为 2,1 的气球,第二支箭的射穿高度为 5,4,3 的气球

这题为P6531升级版,求这题怎么做

1<=n<=10^5

2020/10/7 23:45
加载中...