蓝桥杯备赛：Day8-小红杀怪

📚 算法笔记：小红杀怪 (枚举与最优决策)

1. 题目简述

D-小红杀怪_2024BistuACM萌新练习赛01

• 场景：面对两只血量分别为a , b a, ba,b的怪物。
• 技能 1 (火球术)：对单体造成x xx伤害，消耗 1 次技能。
• 技能 2 (烈焰风暴)：对全体造成y yy伤害，消耗 1 次技能。
• 目标：求击杀两只怪物的最少技能使用次数。
• 数据范围：a , b , x , y ≤ 20 a, b, x, y \le 20a,b,x,y≤20。

2. 核心代码 (C++ 实现)

#include <bits/stdc++.h> using namespace std; // 全局变量建议在 solve 内部重置，防止多组数据干扰 int min_ops = 1000; void solve() { int a, b, x, y; if(!(cin >> a >> b >> x >> y)) return; // 核心思维：枚举。因为血量和伤害都很小，群体技能的使用次数一定在 [0, 20] 之间 for(int k = 0; k <= 20; k++) { // 1. 假设使用了 k 次群体技能后，两只怪物的剩余血量 int rem_a = max(0, a - k * y); int rem_b = max(0, b - k * y); // 2. 剩下的血量只能用单体技能“补刀”，计算各自需要的次数 (向上取整) int ops_a = (rem_a + x - 1) / x; int ops_b = (rem_b + x - 1) / x; // 3. 总次数 = 群体次数 k + 第一只怪补刀次数 + 第二只怪补刀次数 int current_ops = k + ops_a + ops_b; // 更新全局最小值 min_ops = min(min_ops, current_ops); } cout << min_ops << endl; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int _ = 1; while(_--) { solve(); } return 0; }

3. 核心考点与注意事项

• 枚举策略选择：当存在多种决策（单体 vs 群体）且其中一种决策的范围非常小时，优先枚举该决策。本题中枚举“群体攻击次数k kk”后，剩下的单体攻击次数是唯一确定的，从而简化了搜索空间。
• 向上取整公式：在处理“伤害补刀”时，经常需要计算⌈ 血量 伤害 ⌉ \lceil \frac{血量}{伤害} \rceil⌈伤害血量​⌉。在 C++ 整数运算中，公式为(a + b - 1) / b。
• 边界处理：剩余血量rem_a和rem_b必须与0取max，防止出现负数血量导致补刀次数算出负值的逻辑错误。