深海潜艇探险

题意

一艘潜艇初始能量为 $E$ ，要穿越 $n$ 个危险区域。第 $i$ 个区域穿越时消耗 $c_i$ 能量，穿越后补充 $g_i$ 能量。驾驶员可以自由选择穿越顺序，但全程能量必须严格大于 0。问是否存在一种顺序能安全通过所有区域。

思路

自由选择顺序——典型的贪心调度问题。关键是怎么排序才能让能量尽可能"安全"。

先想一个直觉： 如果某个区域"赚能量"（ $g_i \geq c_i$ ），那当然越早做越好，这样后面的能量越充裕。反过来，如果某个区域"亏能量"（ $g_i < c_i$ ），应该放到最后做，趁能量高的时候硬扛。

所以第一步很自然：把区域分成两组，一组是"收益区"（ $g_i \geq c_i$ ），一组是"消耗区"（ $g_i < c_i$ ）。收益区先做，消耗区后做。

收益区内部怎么排？ 都是赚能量的区域，做完之后能量只增不减。瓶颈在于穿越时消耗的 $c_i$ ——万一当前能量不够 $c_i$ 就挂了。所以 $c_i$ 小的先做，风险最低。

消耗区内部怎么排？ 这组做完能量一定会下降。考虑两个区域 A 和 B，先做 A 再做 B 的条件是：

$ $E > c_A \quad \text{且} \quad E - c_A + g_A > c_B$ $

先做 B 再做 A 的条件是：

$ $E > c_B \quad \text{且} \quad E - c_B + g_B > c_A$ $

两种方案对总能量的最终影响一样（都减去 $c_A + c_B - g_A - g_B$ ），区别在于中间的最低点。可以证明，按 $g_i$ 从大到小排序是最优的—— $g_i$ 大的先做，做完能补回更多能量，给后面留更多余量。

为什么按 $g_i$ 降序？ 直觉上，消耗区每做一个能量就会净减少，你希望前面做的那些能"回血"多一点，把后面的能量底线抬高。如果把回血少的放前面，后面的起点更低，更容易崩。

复杂度

时间： $O(n \log n)$ ，排序为主
空间： $O(n)$

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        long long n, E;
        scanf("%lld%lld",&n,&E);
        vector<pair<long long,long long>> gain, lose;
        for(int i=0;i<n;i++){
            long long c,g;
            scanf("%lld%lld",&c,&g);
            if(g >= c) gain.push_back({c,g});
            else lose.push_back({c,g});
        }
        sort(gain.begin(), gain.end(), [](auto&a, auto&b){
            return a.first < b.first;
        });
        sort(lose.begin(), lose.end(), [](auto&a, auto&b){
            return a.second > b.second;
        });
        bool ok = true;
        long long cur = E;
        for(auto&[c,g]:gain){
            if(cur <= c){ ok=false; break; }
            cur = cur - c + g;
        }
        if(ok){
            for(auto&[c,g]:lose){
                if(cur <= c){ ok=false; break; }
                cur = cur - c + g;
            }
        }
        printf("%s\n", ok?"Yes":"No");
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            long E = Long.parseLong(st.nextToken());
            List<long[]> gain = new ArrayList<>();
            List<long[]> lose = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                long c = Long.parseLong(st.nextToken());
                long g = Long.parseLong(st.nextToken());
                if (g >= c) gain.add(new long[]{c, g});
                else lose.add(new long[]{c, g});
            }
            gain.sort((a, b) -> Long.compare(a[0], b[0]));
            lose.sort((a, b) -> Long.compare(b[1], a[1]));
            long cur = E;
            boolean ok = true;
            for (long[] z : gain) {
                if (cur <= z[0]) { ok = false; break; }
                cur = cur - z[0] + z[1];
            }
            if (ok) {
                for (long[] z : lose) {
                    if (cur <= z[0]) { ok = false; break; }
                    cur = cur - z[0] + z[1];
                }
            }
            sb.append(ok ? "Yes" : "No").append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n, E = map(int, input().split())
    gain = []
    lose = []
    for i in range(n):
        c, g = map(int, input().split())
        if g >= c:
            gain.append((c, g))
        else:
            lose.append((c, g))
    gain.sort(key=lambda x: x[0])
    lose.sort(key=lambda x: -x[1])
    cur = E
    ok = True
    for c, g in gain:
        if cur <= c:
            ok = False
            break
        cur = cur - c + g
    if ok:
        for c, g in lose:
            if cur <= c:
                ok = False
                break
            cur = cur - c + g
    print("Yes" if ok else "No")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    let T = parseInt(lines[idx++]);
    const res = [];
    while (T-- > 0) {
        const [n, E] = lines[idx++].split(' ').map(Number);
        const gain = [], lose = [];
        for (let i = 0; i < n; i++) {
            const [c, g] = lines[idx++].split(' ').map(Number);
            if (g >= c) gain.push([c, g]);
            else lose.push([c, g]);
        }
        gain.sort((a, b) => a[0] - b[0]);
        lose.sort((a, b) => b[1] - a[1]);
        let cur = E;
        let ok = true;
        for (const [c, g] of gain) {
            if (cur <= c) { ok = false; break; }
            cur = cur - c + g;
        }
        if (ok) {
            for (const [c, g] of lose) {
                if (cur <= c) { ok = false; break; }
                cur = cur - c + g;
            }
        }
        res.push(ok ? "Yes" : "No");
    }
    console.log(res.join('\n'));
});