F. 最终 Boss – 详细题解

问题重述

你拥有 $n$ 种技能，第 $i$ 种技能每次造成 $a_i$ 点伤害，使用后需要冷却 $c_i$ 回合（即第 $x$ 回合使用后，下一次可用回合为 $x + c_i$）。所有技能初始可用。每个回合你可以同时使用所有不在冷却中的技能。Boss 有 $h$ 点生命值，求击败 Boss 所需的最少回合数。

关键观察

由于技能使用是周期性的，第 $i$ 个技能在回合 $t$ 可用当且仅当 $t \equiv 1 \pmod{c_i}$（因为首次可用在回合 $1$，之后每隔 $c_i$ 回合一次）。更准确地说，在前 $T$ 回合中（$T \ge 1$），技能 $i$ 可使用的次数为：

$$\text{cnt}_i(T) = 1 + \left\lfloor \frac{T-1}{c_i} \right\rfloor $$

造成总伤害为：

$$\text{total}(T) = \sum_{i=1}^n a_i \cdot \left(1 + \left\lfloor \frac{T-1}{c_i} \right\rfloor\right) $$

显然 $\text{total}(T)$ 是 $T$ 的单调不减函数。我们要找到最小的 $T$ 使得 $\text{total}(T) \ge h$。

解法：二分答案

由于 $n$ 和 $h$ 的最大值均为 $2\times 10^5$，而 $T$ 可能很大（最坏情况 $a_i = 1$，$c_i = 2\times 10^5$，$h = 2\times 10^5$，则 $T \approx h \cdot c_i = 4\times 10^{10}$），直接模拟不可行。采用二分法：

• 下界 $L = 1$。
• 上界 $R$ 可取一个足够大的数，例如 $10^{15}$ 或更精确地 $h \cdot \max(c_i) + 1$。由于 $h \le 2\times 10^5$，$\max(c_i) \le 2\times 10^5$，乘积不大于 $4\times 10^{10}$，所以 $R = 10^{15}$ 是安全的。
• 二分判断函数 $\text{check}(T)$：计算 $\text{total}(T)$，若 $\ge h$ 则返回真，否则假。注意计算过程中可能溢出 $64$ 位整数，可使用 __int128 或提前判断累加值已超过 $h$ 后立即返回（因为 $h$ 本身 $\le 2\times 10^5$，累加时一旦达到 $h$ 就可停止，不会溢出，但为通用性仍建议使用 __int128 或直接使用 long long 注意上限：$a_i$ 最大 $2\times 10^5$，$T$ 最大 $4\times 10^{10}$，乘积 $8\times 10^{15}$，而 long long 最大值约 $9.2\times 10^{18}$，所以单次乘法不会溢出，但求和最多 $n$ 项，总伤害可能超过 long long，但由于 $h$ 很小，我们只需累加到 $h$ 即可，因此用 long long 完全安全，提前返回即可避免大数累加。
• 二分结束后，$L$ 即为最小回合数。

复杂度

每个测试用例二分 $O(\log T)$ 次，每次判断 $O(n)$，总复杂度 $O(n \log T)$。$\sum n \le 2\times 10^5$，$\log T \approx 36$，运行时间很短。

注意点

• 二分上界要足够大，确保答案在区间内。
• 使用 $64$ 位整数或 __int128 防止中间计算溢出。
• 当 $h$ 很小时，答案可能为 $1$，二分需正确处理。

示例验证

例1：$h=3, n=2, a=[2,1], c=[2,1]$

• $T=1$：$\text{cnt}_1=1, \text{cnt}_2=1$，总伤害 $3 \ge 3$ → 答案 $1$。

例2：$h=5, a=[2,1], c=[2,1]$

• $T=2$：$\text{cnt}_1=1, \text{cnt}_2=1+(2-1)/1=2$，总伤害 $2\times1 + 1\times2 = 4 < 5$。
• $T=3$：$\text{cnt}_1=1+(3-1)/2=2$，$\text{cnt}_2=1+(3-1)/1=3$，总伤害 $4+3=7 \ge 5$ → 答案 $3$。

与题目输出一致。

结论

本题通过二分答案并利用周期公式直接计算总伤害，避免了模拟每个回合，是解决这类“周期性攻击”问题的标准方法。注意数据范围和溢出处理即可。