1. 解题核心思路
要让AC狗能击败所有龙,最优策略是按龙的力量值从小到大依次挑战:
* 先打最弱的龙,获胜后获得力量加成,让自身力量快速提升;
* 若先打强龙,初始力量不足会直接失败,而从小到大打能最大化生存概率。
核心步骤:
1. 输入测试用例数,遍历每个测试用例;
2. 读取初始力量s和龙的数量n;
3. 存储每条龙的力量值x和奖励值y;
4. 按龙的力量值x升序排序;
5. 依次挑战排序后的龙:若当前力量>龙的力量,击败后加奖励;否则失败;
6. 输出最终结果(YES/NO)。
2. 代码逐行解析
3. 测试用例验证
以题目输入为例:
输入1:
执行过程:
* 第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. 代码优化(可选)
原代码有少量冗余,优化后更简洁:
5.总结
1. 核心策略:必须按龙的力量值从小到大挑战,这是能击败所有龙的最优解;
2. 关键步骤:读取数据 → 排序龙的信息 → 依次挑战并更新力量 → 判断结果;
3. 易错点:排序规则要正确(升序)、判断条件是s > 龙的力量(而非≥)、及时break减少无效循环。
这段代码的逻辑完全贴合题目要求,通过贪心策略(每次选最优解)保证了正确性,同时时间复杂度为O(n log n)(主要来自排序),能轻松处理n≤1000的限制。