自选题解 | 闯关

1. 解题核心思路

要让AC狗能击败所有龙，最优策略是按龙的力量值从小到大依次挑战：

• 先打最弱的龙，获胜后获得力量加成，让自身力量快速提升；
• 若先打强龙，初始力量不足会直接失败，而从小到大打能最大化生存概率。
  核心步骤：

1. 输入测试用例数，遍历每个测试用例；
2. 读取初始力量s和龙的数量n；
3. 存储每条龙的力量值x和奖励值y；
4. 按龙的力量值x升序排序；
5. 依次挑战排序后的龙：若当前力量>龙的力量，击败后加奖励；否则失败；
6. 输出最终结果（YES/NO）。

2. 代码逐行解析

#include <bits/stdc++.h>  // 万能头文件，包含所有常用STL库（如sort、cin/cout等）
using namespace std;      // 使用std命名空间，避免重复写std::

// 定义结构体存储每条龙的信息：x是龙的力量值，y是击败后获得的奖励
struct str {
    int x;
    int y;
}a[1010];  // 定义结构体数组a，最多存储1010条龙（满足n≤1000的限制）

// 排序规则函数：按龙的力量值x从小到大排序（sort的自定义比较规则）
bool cmp (str fzt, str hzt) {            // fzt是作者的名字首字母，hzt是作者的女同学。
    return fzt.x < hzt.x;  // 返回true时，fzt排在hzt前面
}

int main () {
    int t;
    cin >> t;  // 输入测试用例数量T
    while (t--) {  // 遍历每个测试用例（t次循环，每次处理一个用例）
        int s, n;
        cin >> s >> n; 
        
        // 读取n条龙的信息，存入结构体数组a（下标从1开始，符合日常计数习惯）
        for (int i = 1;i <= n;i++) {
            cin >> a[i].x >> a[i].y;
        }
        
        // 对数组a的1~n位置排序，按cmp规则（龙的力量值升序）
        sort (a + 1, a + n + 1, cmp);
        
        bool ok = 1;  // 标记是否能击败所有龙，初始为true（1）
        for (int i = 1; i <= n; i++) {  // 依次挑战排序后的龙
            if (s > a[i].x) {  // 当前力量>龙的力量，能击败
                s += a[i].y;   // 获得奖励，更新自身力量
            }else{             // 力量不足，无法击败
                ok = 0;        // 标记为失败
                break;         // 无需继续挑战，直接退出循环
            }
        }
        
        // 根据ok的值输出结果
        if (ok) {
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

3. 测试用例验证

以题目输入为例：
输入1：

2
2 2
1 99
100 0
10 1
100 100

执行过程：

• 第1个测试用例：
  • 初始s=2，n=2；
  • 两条龙信息：(1,99)、(100,0)，排序后还是这顺序；
  • 挑战第1条龙：2>1 → s=2+99=101；
  • 挑战第2条龙：101>100 → s=101+0=101；
  • 所有龙击败，输出YES。
• 第2个测试用例：
  • 初始s=10，n=1；
  • 龙信息：(100,100)；
  • 挑战：10不大于100 → ok=0，输出NO。

4. 代码优化（可选）

原代码有少量冗余，优化后更简洁：

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

struct Dragon {
    int power;  // 龙的力量值（更语义化的命名）
    int reward; // 击败奖励
};

// 排序规则：按龙的力量值升序
bool compare(const Dragon& a, const Dragon& b) {
    return a.power < b.power;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int s, n;
        cin >> s >> n;
        vector<Dragon> dragons(n);  // 用vector更灵活，无需固定大小
        for (int i = 0; i < n; ++i) {  // 下标从0开始（C++习惯）
            cin >> dragons[i].power >> dragons[i].reward;
        }
        sort(dragons.begin(), dragons.end(), compare);
        
        bool canWin = true;
        for (const auto& d : dragons) {  // 范围for循环，更简洁
            if (s > d.power) {
                s += d.reward;
            } else {
                canWin = false;
                break;
            }
        }
        cout << (canWin ? "YES" : "NO") << endl;
    }
    return 0;
}

5.总结

1. 核心策略：必须按龙的力量值从小到大挑战，这是能击败所有龙的最优解；
2. 关键步骤：读取数据 → 排序龙的信息 → 依次挑战并更新力量 → 判断结果；
3. 易错点：排序规则要正确（升序）、判断条件是s > 龙的力量（而非≥）、及时break减少无效循环。

这段代码的逻辑完全贴合题目要求，通过贪心策略（每次选最优解）保证了正确性，同时时间复杂度为O(n log n)（主要来自排序），能轻松处理n≤1000的限制。