华为 · 贪心 · 算法编程题
华为 贪心 n ≤ 1e5 时限 5 秒 / 512 MB

题目描述

一艘高科技深海潜艇正在执行一项对未知海沟的探险任务。在它的航线上，分布着 n 个地质活动异常的危险区域。
潜艇的初始能量储备为 m 。对于第 i 个危险区域，潜艇需要消耗 a_i 的能量才能安全通过；在成功通过后，潜艇可以利用该区域尽头的海底热泉补充 b_i 的能量。
能量的消耗 ( a_i ) 发生在穿越过程中，而能量的补充 ( b_i ) 必须在完全穿越该区域后才能进行。潜艇的驾驶员可以自由规划穿越这 n 个区域的顺序。
任务成功的条件是，在穿越所有区域的整个过程中，潜艇的能量值必须始终大于 0。如果在穿越任何一个区域的过程中，潜艇的能量值 E 满足 E ≤ 0 ，任务就会因能量耗尽而失败。
请判断，是否存在一个安全的航行顺序，能让潜艇成功完成这次探险任务。

输入输出

输入描述
第一行包含一个整数 T ( 1 ≤ T ≤ 10 )，代表测试数据的组数。
对于每组测试数据：
- 第一行包含两个整数 n 和 m ( 1 ≤ n, m ≤ 10^5 )，分别代表危险区域的数量和潜艇的初始能量。
- 接下来 n 行，每行包含两个整数 a_i 和 b_i ( 0 ≤ a_i, b_i ≤ 10^5 )，分别代表穿越第 i 个区域的能量消耗和补充量。
- 注意：每一对 (a_i, b_i) 是绑定的，但穿越的顺序可以自由安排。
输出描述
对于每组测试数据，如果存在一个安全的航行顺序，则输出 Yes ，否则输出 No 。

样例共 1 组

样例 1
输入
2
2 5
3 2
4 5
2 5
3 2
4 2
输出
Yes
No

算法解析依据充分

考点：贪心

数据规模 n ≤ 1e5 ｜ 限制 5 秒 / 512MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5，m ≤ 1e5，T ≤ 10
  • 元素值域：a_i ≤ 1e5，b_i ≤ 1e5（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：5 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

经典能量贪心：a_i ≤ b_i 的一组按 a_i 升序、a_i > b_i 的一组按 b_i 降序，排好序后顺序模拟，全程能量恒 >0 即 Yes；n≤1e5 必须用排序而非搜索。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：2 / 2 5 / 3 2 / 4 5 / 2 5 / 3 2 / 4 2
  • 输出：Yes / No

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月10号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解