解题思路

• 有初始清醒值 m，第 i 个咒语先扣 a_i，若此时 m-a_i<=0 则失败；若存活，再加 b_i，即 m ← m - a_i + b_i。
• 目标：调整施法顺序，使全过程都不失败。

贪心策略（经典“阈值+收益”排序）：

1. 把咒语分成两类：

   • A 类：a_i <= b_i（净不亏或增益）。
   • B 类：a_i > b_i（净亏）。

2. 先做 A 类，并按 a_i 升序执行。理由：门槛越小越先做，不会让后续更难（交换论证）。

3. 再做 B 类，并按 b_i 降序（若需再按 a_i 升序打破平局）。理由：净亏时希望“回血”多的在前，让剩余清醒值尽量大以通过后续更高门槛。

4. 过程检查：每次执行前必须满足 m > a_i，否则输出 No；全部通过则 Yes。 使用 64 位整型保存 m（可能增长很多）。

复杂度分析

• 排序主导：O(n log n)；线性扫描更新：O(n)。
• 额外空间：用于分组与排序的容器，O(n)。

代码实现

Python

import sys

def can_escape(n, m, items):
    up, down = [], []
    for a, b in items:
        (up if a <= b else down).append((a, b))
    # 先做不亏或增益的，按门槛升序
    up.sort(key=lambda x: x[0])
    for a, b in up:
        if m > a:
            m += b - a
        else:
            return False
    # 再做净亏的，按b降序，a升序
    down.sort(key=lambda x: (-x[1], x[0]))
    for a, b in down:
        if m > a:
            m += b - a
        else:
            return False
    return True

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t, i = data[0], 1
    out = []
    for _ in range(t):
        n, m = data[i], data[i+1]; i += 2
        items = []
        for _ in range(n):
            a, b = data[i], data[i+1]; i += 2
            items.append((a, b))
        out.append("Yes" if can_escape(n, m, items) else "No")
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

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

/** ACM 风格主类 */
public class Main {

    // 判断是否可逃脱的核心函数
    static boolean canEscape(int n, long m, int[] a, int[] b) {
        List<int[]> up = new ArrayList<>();
        List<int[]> down = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (a[i] <= b[i]) up.add(new int[]{a[i], b[i]});
            else down.add(new int[]{a[i], b[i]});
        }
        // A类：按a升序
        up.sort(Comparator.comparingInt(x -> x[0]));
        for (int[] x : up) {
            int A = x[0], B = x[1];
            if (m > A) m += (long)B - A;
            else return false;
        }
        // B类：按b降序，a升序
        down.sort((x, y) -> {
            if (x[1] != y[1]) return Integer.compare(y[1], x[1]);
            return Integer.compare(x[0], y[0]);
        });
        for (int[] x : down) {
            int A = x[0], B = x[1];
            if (m > A) m += (long)B - A;
            else return false;
        }
        return true;
    }

    // 快速读入（数据量较大）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, s = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { s = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * s;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt();
            long m = fs.nextInt();
            int[] a = new int[n], b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = fs.nextInt();
                b[i] = fs.nextInt();
            }
            sb.append(canEscape(n, m, a, b) ? "Yes" : "No").append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

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

// 判断是否可逃脱的核心函数
bool canEscape(int n, long long m, const vector<pair<int,int>>& items) {
    vector<pair<int,int>> up, down;
    up.reserve(n); down.reserve(n);
    for (auto [a,b] : items) {
        if (a <= b) up.push_back({a,b});
        else down.push_back({a,b});
    }
    // A类：按a升序
    sort(up.begin(), up.end(), [](auto &x, auto &y){ return x.first < y.first; });
    for (auto [a,b] : up) {
        if (m > a) m += (long long)b - a;
        else return false;
    }
    // B类：按b降序，a升序
    sort(down.begin(), down.end(), [](auto &x, auto &y){
        if (x.second != y.second) return x.second > y.second;
        return x.first < y.first;
    });
    for (auto [a,b] : down) {
        if (m > a) m += (long long)b - a;
        else return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if(!(cin >> T)) return 0;
    while (T--) {
        int n; long long m;
        cin >> n >> m;
        vector<pair<int,int>> items(n);
        for (int i = 0; i < n; ++i) {
            int a, b; cin >> a >> b;
            items[i] = {a, b};
        }
        cout << (canEscape(n, m, items) ? "Yes" : "No") << "\n";
    }
    return 0;
}

题目内容

魔法学院的某学员有一天早上准备起床的时候，突然发现有人在他的被子上施加了 $n$ 道昏睡魔法，被子上每道魔法施加完毕后该学员都会减少 $a_i$ 点清醒值，而该学员每一次面对魔法都会进行抵抗，使自己的清醒值增加 $b_i$ (只有当被子施法完成后才增加)，初始时该学员的清醒值为 $m$ 。

而该学员作为魔法学院的学生也不是吃素的，他有一道魔法可以指定被子的施法顺序，但因为他有点紧张所以很难冷静思考，你能帮忙看看是否该学员可以挣脱被子的昏睡魔法吗?

如果被子的昏睡魔法以某种顺序施法时，若存在某一次施法后该学员的清醒值 $≤0$ ，则认为该学员挣脱失败。

输入描述

第一行一个整数 $T(1≤T≤10)$ ，表示数据组数。

对于每一组数据，第一行两个整数 $n$ 和 $m(1≤n,m≤10^5)$ ，分别表示被子上被施加的昏睡魔法次数和学员的初始清醒值。

接下来 $n$ 行每行两个整数 $a_i$ 和 $b_i(0≤a_i,b_i≤10^5)$ ，分别表示本次昏睡魔法减少的清醒值和学员抵抗后增加的清醒值。

(请注意，每一行 $a_i$ 和 $b_i$ 互相绑定，不可调换，但是施法的顺序可以调换)

输出描述

对于每一组数据，如果学员能逃脱，输出 $YES$ ，反之输出 $NO$ 。

样例1

输入

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

输出

Yes
No

说明

输入 $2$ 组数据

第一组数据，施加 $2$ 道魔法，初始清醒值为 $5$

假设先抵抗第一道魔法：$5-3+2=4$，抵抗第二道魔法时 $4-4≤=0$，

假设先抵抗第二道魔法：$5-4+5=6$，抵抗第一道魔法时 $6-3+2≤=5$，

所以先抵抗第二道魔法，可以挣脱。

第二组数据，施加 $2$ 道魔法，初始清醒值为 $5$

假设先抵抗第一道魔法：$5-3+2=4$ ，抵抗第二道魔法时 $4-4≤=0$，

假设先抵抗第二道魔法：$5-4+2=3$ ，抵抗第一道魔法时 $3-3≤=0$ ,

所以无论施加的魔法是哪个顺序，都会在两道魔法施加完毕后清醒值归零，从而挣脱失败。