Codeforces 230A：Dragons 贪心与排序
题意与词汇
Kirito 初始战斗力为 s，这一关有 n 条龙。第 i 条龙的战斗力是 x_i，击败它后可以获得 y_i 点战斗力加成。
strength：战斗力，由整数表示；duel：决斗；equals s：初始战斗力等于s，这里是在说明初始值；the i-th dragon：第i条龙，i从 1 到n。
关键规则是严格比较：只有当前战斗力 大于 龙的战斗力，才能获胜。如果当前战斗力不大于 x_i，就不能挑战这条龙。击败后再把奖励加到自己的战斗力上。
贪心思路：先挑战弱的龙
把每条龙看成一组数据 (x_i, y_i)，按 x_i 从小到大排序，然后依次挑战：
- 如果当前战斗力
s <= x_i，输出NO； - 否则击败这条龙，并令
s += y_i； - 所有龙都打完，输出
YES。
这样安排不会吃亏：奖励 y_i 不会让战斗力下降，所以先打较弱的龙只会保持或增加后续战斗力。如果连当前最弱的龙都打不过，其他战斗力更高的龙也打不过。题目保证每条龙的奖励非负，因此升序贪心成立。
从 C 思维迁移到 C++
本题把每条龙的两个属性放在一起处理，适合用结构体：
struct Dragon {
int strength;
int bonus;
};
再用 vector<Dragon> 保存所有龙。读取时直接给每个结构体成员赋值，排序时传入比较函数。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Dragon {
int strength;
int bonus;
};
bool cmp(const Dragon& a, const Dragon& b) {
return a.strength < b.strength;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int s, n;
cin >> s >> n;
vector<Dragon> dragons(n);
for (Dragon& dragon : dragons) {
cin >> dragon.strength >> dragon.bonus;
}
sort(dragons.begin(), dragons.end(), cmp);
for (const Dragon& dragon : dragons) {
if (s <= dragon.strength) {
cout << "NO" << endl;
return 0;
}
s += dragon.bonus;
}
cout << "YES" << endl;
return 0;
}
这次卡住的几个 C++ 规则
1. 类型先定义，后使用
cmp 的参数类型是 Dragon，所以编译器在读到比较函数前，必须已经认识 Dragon。最直观的顺序是：
struct Dragon {
int strength;
int bonus;
};
bool cmp(const Dragon& a, const Dragon& b) {
return a.strength < b.strength;
}
如果把 cmp 放在结构体定义前，常见报错是：
'Dragon' was not declared in this scope
2. sort 的第三个参数是比较规则
sort 默认按 < 比较元素，不是只能处理 int 或 string。但 Dragon 是自定义类型，如果没有定义 operator<，编译器就不知道两个 Dragon 谁更小。
因此这里把比较函数作为第三个实参传入：
sort(dragons.begin(), dragons.end(), cmp);
比较函数也可以写成 lambda：
sort(dragons.begin(), dragons.end(),
[](const Dragon& a, const Dragon& b) {
return a.strength < b.strength;
});
两种写法选一种即可。传入自定义比较器后，不需要再为 Dragon 定义 operator<。
3. 比较函数和 sort 调用是分开的
sort(...) 是一次函数调用，调用后用分号结束；不能把比较函数的函数体接在调用后面。
bool cmp(const Dragon& a, const Dragon& b) {
return a.strength < b.strength;
}
sort(dragons.begin(), dragons.end(), cmp);
4. const Dragon& 表示只读引用
遍历时使用 const Dragon& 不会复制整个结构体，也保证循环中不会意外修改龙的数据。排序比较函数同样用引用接收元素；对这道小题而言按值也能工作，但引用是更通用的写法。
看模板报错时先抓住第一处错误
这次真正有用的信息是最前面的错误，例如：
'Dragon' was not declared in this scope
expected ';' before '{'
先修正第一、第二个错误，再重新编译。后面很长的 vector 或 sort 内部模板报错，往往只是前面语法或类型错误引发的连锁反应。
Windows 编译运行
g++ -std=c++20 230A.cpp -o 230A.exe
.\230A.exe
标准选项应写成 -std=c++20，而不是 -stdc++=20。如果出现 Permission denied，先确认 230A.exe 没有仍在运行；运行中的程序可能占用该文件，导致编译器无法覆盖它。若关闭程序后仍报错，再检查目录写入权限和杀毒软件拦截。
复杂度与记忆主线
- 排序：
O(n log n)； - 顺序挑战：
O(n)； - 存储所有龙：
O(n)。
定义 Dragon
→ 用 vector<Dragon> 读入 (strength, bonus)
→ 按 strength 升序 sort
→ 检查当前战斗力是否严格大于龙的 strength
→ 能打就加 bonus，打不过就 NO
→ 全部打完就是 YES
这题真正练到的不只是贪心，而是 struct → vector<Dragon> → cin 读成员 → sort 自定义比较 → 遍历更新 这一整套 C++ 竞赛写法。