E. 每秒伤害 详细题解

题目核心理解

你有 $k$ 个技能点，可以分配给单次伤害 $x$ 和每秒攻击次数 $y$，满足：

• $x,y$ 均为正整数
• $x+y \le k$

击杀第 $i$ 只怪物需要 $\lceil \dfrac{h_i}{x} \rceil$ 次攻击，总攻击次数为：

$$f(x)=\sum_{i=1}^n \left\lceil \frac{h_i}{x} \right\rceil $$

总时间为 $\dfrac{f(x)}{y}$，即 $\dfrac{f(x)}{k-x}$。

目标：选择 $x$ 使得总时间最小，输出对应的 $x,y$。

---

核心思路

1. 关键性质

• 忽略上取整时，$\dfrac{H}{x(k-x)}$ 是时间的下界，其最小值在 $x=\dfrac{k}{2}$ 处。
• 最优解几乎一定出现在 $k/2$ 附近很小的范围内。
• 远离中心点的 $x$ 可以直接用下界剪枝跳过，无需计算。

2. 快速计算规则

对给定 $x$，计算 $f(x)$ 的方式：

• 将 $h$ 降序排序。
• 前一部分较大的值暴力累加。
• 后一部分值重复较多，用二分分段统计，避免 $O(n)$ 遍历。

3. 枚举规则

• 从中心点 $mid=k/2$ 开始，由近到远枚举 $x$。
• 对每个 $x$，先检查下界 $\dfrac{H}{x(k-x)}$，若已大于当前最优则直接跳过。
• 否则计算真实时间，更新最优解。

---

算法流程

1. 将 $h$ 数组降序排序，计算总血量 $H=\sum h_i$。
2. 设中心点 $mid=k/2$，以它为初始最优解。
3. 按距离 $mid$ 从小到大枚举所有合法 $x\in[1,k-1]$。
4. 对每个 $x$：
   • 若下界 $\dfrac{H}{x(k-x)} \ge$ 当前最优时间，跳过。
   • 否则分段计算 $f(x)$，得到真实时间 $g(x)=\dfrac{f(x)}{k-x}$。
   • 若更优，则更新最优 $x$。
5. 输出最优的 $x$ 和 $y=k-x$。

---

公式与复杂度分析

总攻击次数：

$$f(x)=\sum_{i=1}^n\left\lceil\frac{h_i}{x}\right\rceil $$

总时间：

$$g(x)=\frac{f(x)}{k-x}$$

时间下界：

$$g(x)\ge \frac{H}{x(k-x)}$$

复杂度

• 排序：$O(n\log n)$
• 枚举 + 计算：$O(\sqrt{n\log n}\cdot k)$
• 总时间复杂度：$O(n\log n + \sqrt{n\log n}\cdot k)$

可轻松处理 $n,k\le 2\times 10^5$、$h_i\le 10^{13}$ 的数据范围，在 $5$ 秒时限内稳定通过。