Final Boss
您正在面对您最喜欢的游戏中的最终Boss。敌人的生命值为 $h$ 。你的角色有 $n$ 次攻击。第 $i$ 次攻击会对敌人造成 $a_i$ 的伤害,但冷却时间为 $c_i$ 个回合,也就是说,如果你当前的回合是 $c_i$
,那么下一次使用该攻击的时间是 $x + c_i$ 个回合。每个回合,你都可以同时使用当前未冷却的所有攻击。如果所有攻击都处于冷却状态,则该回合你什么也不做,跳到下一回合。最初,所有攻击都不在冷却时间内。最少要花多少回合才能打败Boss?当Boss的生命值为 $0$ 或更低时,它就被击败了。
分析:
时间复杂度为
$\mathcal{O(n \log {(h \cdot \max c_i)})}$
计算当前回合 $mid$ 所能造成的伤害
$$ \displaystyle \sum_{i=1}^{n}{a_i\left( \lfloor\frac{mid - 1}{c_i}\rfloor + 1 \right)} $$
与 $h$ 进行比较,再更新左右边界的值,用一个变量保存最小回合数。