B3628 机器猫斗恶龙 題解

ShanCreeperPro · 2022-05-21 13:31:11 · 题解

B3628 机器猫斗恶龙 題解

管理员注：

阅读本文章前，请先阅读 \ \texttt{ShanCreeper} B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

观察题目，可以看出初始血量越多，越可能成功的性质。

具体的，如果答案为 k：

• 而 k,k+1,... 的血量会成功。

问题就变成了找到第一个能成功的血量，显而易见的二分。

我们不断猜测 \texttt{mid}，暴力模拟：

• 如果 x 的血量能完成任务，则答案 \leq x；
• 如果不能完成任务，则答案 >x。

所以我们可以写一个函数 check 判断 x 血量是否能完成，然后进行二分。