首页 > 试题广场 >

深海潜艇探险

[编程题]深海潜艇探险
  • 热度指数: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 整理上传
头像 爱吃鸡腿的猫头鹰又被画饼了
发表于 2025-10-11 17:57:44
#include <bits/stdc++.h> #include <csetjmp> #include <vector> using namespace std; //buff bool up(pair<int, int>& a, pai 展开全文
头像 Silencer76
发表于 2025-10-11 18:02:24
题目链接 深海潜艇探险 题目描述 一艘潜艇拥有初始能量 ,需要穿越 个危险区域。每个区域 有一个能量消耗 和一个能量补充 。 规则: 潜艇可以自由决定穿越 个区域的顺序。 要穿越区域 ,潜艇当前能量必须严格大于消耗 。 成功穿越后,潜艇的能量变为 当前能量 - c_i + r_i。 任务目 展开全文