首页 > 试题广场 >

深海潜艇探险

[编程题]深海潜艇探险
  • 热度指数:220 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
一艘高科技深海潜艇正在执行一项对未知海沟的探险任务。在它的航线上,分布着 n 个地质活动异常的危险区域。
潜艇的初始能量储备为 m。对于第 i 个危险区域,潜艇需要消耗 a_i 的能量才能安全通过;在成功通过后,潜艇可以利用该区域尽头的海底热泉补充 b_i 的能量。
能量的消耗 (a_i) 发生在穿越过程中,而能量的补充 (b_i) 必须在完全穿越该区域后才能进行。潜艇的驾驶员可以自由规划穿越这 n 个区域的顺序。
任务成功的条件是,在穿越所有区域的整个过程中,潜艇的能量值必须始终大于 0。如果在穿越任何一个区域的过程中,潜艇的能量值 E 满足 E \le 0,任务就会因能量耗尽而失败。
请判断,是否存在一个安全的航行顺序,能让潜艇成功完成这次探险任务。

输入描述:
第一行包含一个整数 T (1 \le T \le 10),代表测试数据的组数。

对于每组测试数据:
- 第一行包含两个整数 nm (1 \le n, m \le 10^5),分别代表危险区域的数量和潜艇的初始能量。
- 接下来 n 行,每行包含两个整数 a_ib_i (0 \le a_i, b_i \le 10^5),分别代表穿越第 i 个区域的能量消耗和补充量。
- 注意:每一对 (a_i, b_i) 是绑定的,但穿越的顺序可以自由安排。


输出描述:
对于每组测试数据,如果存在一个安全的航行顺序,则输出 Yes ,否则输出 No 。
示例1

输入

2
2 5
3 2
4 5
2 5
3 2
4 2

输出

Yes
No

备注:
本题由牛友@Charles 整理上传
没分区,整个排的,过了 20%
发表于 2025-10-12 15:09:38 回复(0)
注意溢出:累积能量m要用Long
发表于 2025-10-12 11:06:56 回复(0)