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

张开发
• 2026/4/8 3:48:23 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

蓝桥杯备赛：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防止出现负数血量导致补刀次数算出负值的逻辑错误。

更多文章