# 战斗属性的升级计划：堆调度

**基于出题人的整除事件与防御单调性。GPT-6 将离线事件表改为每种敌人一个待处理事件的最小堆，降低事件存储空间。**

## 方法

固定攻击升级次数 $x$ 和防御次数 $y$ ，敌人回合数为
$$
t_i=\left\lceil\frac{h_i}{A_0+xV_A-d_i}\right\rceil,
$$
总伤害为 $\sum_i k_it_i\max(a_i-D_0-yV_D,0)$ ，所需生命为总伤害加一与 $H_0$ 的较大者。攻击必须先达到能对每种敌人造成伤害的最小次数。

费用对防御次数离散凸；攻击提高时，额外防御节省的生命费用不增。因此从无伤防御起，只在严格变便宜时降低防御，一个始终左移的指针就能维护最优防御。费用相同时保留更高防御，因为这对应更少的生命。防御桶和精确大整数比较与[主解法](solution.zh.md)相同。

每种敌人至多保留一个事件。若当前回合数 $t_i>1$ ，下一事件的攻击次数为
$$
x_i'=\left\lceil
\frac{d_i+\lceil h_i/(t_i-1)\rceil-A_0}{V_A}
\right\rceil.
$$
将 $(x_i',i)$ 放入最小堆。先评价初始可行攻击，再不断：

1. 取堆中最小的攻击次数 $x$ .
2. 处理所有时间等于 $x$ 的事件，更新对应敌人的回合数及防御桶。
3. 每次处理后按新回合数计算该敌人的下一事件并入堆；回合数已为一则结束其事件链。
4. 移动防御指针，再按 $(\text{费用},H,D,A)$ 更新答案。

初始防御已能完全阻挡的敌人不产生伤害事件，但其防御仍参与初始攻击下界。

## 正确性

事件公式由 $t_i$ 首次下降所需的最小单回合伤害推得，严格晚于当前次数。因此每个敌人的事件链有序，堆始终给出所有敌人的最早未处理变化。处理完同一时刻的全部事件后，所有回合数恰好对应当前攻击。

没有事件的区间内，伤害与最优防御/生命不变，攻击单价为正，故只需区间最左端。防御的凸性和单调性保证指针取到每个候选攻击下的最优解，四元组比较保证全局最优和字典序。

同时攻击仍需计入敌人最后一击；生命必须为总伤害加一。桶值可超过 64 位，程序沿用两段整数和除法界限比较，不引入浮点误差。

## 复杂度与取舍

令 $E=O(\sum_i\sqrt{h_i})$ ，最大防御次数为 $Y$ .堆大小不超过 $n$ ，总时间 $O((n+E)\log n+Y)$ ，空间 $O(n+Y)$ .无需分配攻击次数下标数组或同时保存全部事件。

与事件表相比，堆消除了 $R+E$ 的存储项，但每次事件多了对数调度开销；不是对所有输入都更快。两种方案并列，均可通过当前完整范围；需要较少内存时可用本程序。

[计算程序](alternative-heap.cpp)。