众所周知我是SB
  • 板块学术版
  • 楼主xmtx20081011
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/23 21:46
  • 上次更新2023/10/27 06:13:25
查看原帖
众所周知我是SB
382823
xmtx20081011楼主2022/10/23 21:46

怎么做,求思路

在二维空间中有N个球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。

由于它是水平的,所以Y坐标并不重要,因此只要知道开始和结束的X坐标就足够了。开始坐标总是小于结束坐标。

平面内最多存在10^4个气球。一支弓箭可以沿着X轴从不同点完全垂直地射出。

在坐标X处射出一支箭,若有一个气球的直径的开始和结束坐标为 X[start],X[end], 且满足X[start] ≤ X ≤ X[end],则该气球会被引爆。

可以射出的弓箭的数量没有限制。弓箭一旦被射出之后,可以无限地前进。

我们想找到使得所有气球全部被引爆,所需的弓箭的最小数量。

输入:

第一行有一个正整数N(1<=N<=10000)

接下来有N行,每一行有2个正整数X[start],X[end],分别表示气球的开始X坐标和结束X坐标,1<=X[start]<=X[end]<=100000

输出:

单独一行,表示引爆所有气球所需弓箭的最小数量

【样例输入】:

4

10 16

2 8

1 6

7 12

【样例输出】:

2

【样例解释】:

对于该样例,我们可以在x = 6(射爆[2,8],[1,6]两个气球)和 x = 11(射爆另外两个气球),所需弓箭的数量为2。

2022/10/23 21:46
加载中...