GitHub 源文件 Markdown English

战斗属性的升级计划：题解

出题人解法：整除值变化事件与单调防御指针。GPT-6 补充凸性、平局和整数安全证明，提供标准 C++17 实现及堆调度补充方案。

1. 固定攻击和防御

设攻击、防御的升级次数为 \(x,y\) ，于是

\[ A=A_0+xV_A,\qquad D=D_0+yV_D. \]

必须有 \(A>d_i\) .击败一名第 \(i\) 种敌人要

\[ t_i(x)=\left\lceil\frac{h_i}{A-d_i}\right\rceil \]

回合。因为同时攻击，最后一回合敌人也会造成伤害。全部敌人的总伤害为

\[ F_x(y)=\sum_i k_it_i(x)\max(a_i-D_0-yV_D,0). \]

伤害均非负，不回血，因此战斗顺序不影响生存条件。最小升级后生命为

\[ H=\max(H_0,F_x(y)+1), \]

花费为 \(xC_A+yC_D+(H-H_0)C_H\) .

攻击升级次数只需考虑

\[ L=\max\left(0,\max_i\left\lceil\frac{d_i+1-A_0}{V_A}\right\rceil\right), \quad R=\max\left(0,\max_i\left\lceil\frac{d_i+h_i-A_0}{V_A}\right\rceil\right). \]

低于 \(L\) 无法击败某些敌人，高于 \(R\) 不再减少回合数。防御次数不超过

\[ Y=\max\left(0,\max_i\left\lceil\frac{a_i-D_0}{V_D}\right\rceil\right). \]

达到 \(Y\) 时完全不受伤。即使某类敌人不能造成伤害，也要用它的防御更新攻击下界。

2. 防御的凸性与单调性

固定 \(x\) ，\(F_x(y)\) 是若干非负折线的和，关于整数 \(y\) 离散凸且不增。加血量 \(\max(F_x(y)+1-H_0,0)\) 仍然凸，加入线性的防御价格后，总费用关于 \(y\) 也凸。

从最大防御 \(Y\) 开始，只在减少一次防御能严格减少费用时左移，停在费用最小的最大防御次数。若相邻防御费用相同，较高防御对应更小的生命：防御单价为正，相同总费用必须由更多加血补偿较低防御。因此保留较高防御符合先比较生命的字典序。

攻击提高后，每种敌人的回合数都不增。对于固定相邻防御 \(y-1,y\) ，它们的总伤害差不增，较低防御下的总伤害也不增。加血差等于这两个非负量中的较小者：

\[ \min\left(F_x(y-1)-F_x(y),\ \max(F_x(y-1)+1-H_0,0)\right). \]

所以增加防御的节省额随攻击提高而不增，最大最优防御次数不会向右移动。整个攻击扫描只需一个总共左移 \(Y\) 次的指针。

3. 只在回合数改变时更新

\(\lceil h/d\rceil=\lfloor(h-1)/d\rfloor+1\) 只有 \(O(\sqrt h)\) 个不同值。若当前回合数为 \(t>1\) ，下一次降低回合数所需的最小伤害为

\[ d'=\left\lceil\frac{h}{t-1}\right\rceil. \]

将 \(d'\) 换算成最小攻击升级次数，即

\[ x'=\left\lceil\frac{d_i+d'-A_0}{V_A}\right\rceil. \]

它严格大于当前次数，可能一次跳过多个回合数。重复该过程即可列出每种敌人的全部变化事件。

出题人解法将事件挂到以攻击次数为下标的链表中，顺序扫描。没有事件时，伤害函数不变而攻击费用增加，故只在 \(L\) 和事件位置评价答案。参考程序动态按 \(R\) 分配下标数组，事件数记为 \(E=O(\sum_i\sqrt{h_i})\) .

4. 防御桶

对于会造成伤害的敌人，写

\[ a_i-D_0=p_iV_D+r_i,\qquad 0\le r_i<V_D, \]

令 \(w_i=k_it_i\) .当前防御次数为 \(y\) 时，把 \(p_i\ge y\) 的敌人放入活跃部分，维护它们的 \(T=\sum w_i\) 和当前总伤害 \(F\) .其余按 \(p_i\) 分桶，保存次数和及 \(B_p=\sum_{p_i=p}w_ir_i\) .

防御从 \(y\) 减到 \(y-1\) ，新增伤害为

\[ \Delta=T V_D+B_{y-1}. \]

接受左移后，把这一桶的次数并入 \(T\) .攻击事件使 \(w_i\) 减少；若已活跃，则同步减少 \(T\) 和 \(F\) ，否则更新其桶。所有敌人的事件更新完，再移动防御指针。

5. 精确整数比较

原范围的中间伤害可达 \(6.25\cdot10^{20}\) ，不能全部直接存入 64 位整数，也不能用浮点判断费用平局。参考程序把桶值保存为以 \(10^9\) 为基数的两段整数；单种敌人的更新量至多 \(1.25\cdot10^{17}\) ，可安全逐次加减。

当前加血量记为 \(z=\max(F+1-H_0,0)\) .减少防御严格变优等价于

\[ \max(F+\Delta+1-H_0,0) \le z+\left\lfloor\frac{C_D-1}{C_H}\right\rfloor. \]

令右边允许的新伤害增量为

\[ B=H_0-1+z+\left\lfloor\frac{C_D-1}{C_H}\right\rfloor-F. \]

先精确判断桶值不超过 \(B\) ，再用

\[ T\le\left\lfloor\frac{B-B_{y-1}}{V_D}\right\rfloor \]

判断，不先计算可能溢出的乘积。

对每个攻击值，直接买到无伤防御的花费不超过 \(YC_D\le5\cdot10^{15}\) .指针只接受更便宜的防御/生命组合，所以保存的实际伤害和生命仍在 64 位范围内。攻击花费最多约 \(10^{16}\) ，总费用也安全。超大桶值只有通过范围比较后才转换为单个整数。

每次以完整四元组 \((\text{费用},H,D,A)\) 比较答案，不能遗漏最后的攻击平局。给出的范围内总能升级到可击败且无伤的状态，无须输出不可达的 \(-1\) 分支。

6. 正确性、复杂度与方案比较

战斗公式精确给出每对攻击、防御的最少生命；凸性与单调性保证防御指针取得每个攻击值的最优字典序方案；事件覆盖了所有伤害函数变化点，其间增加攻击只增加费用。枚举这些候选并比较四元组，因而得到全局要求的最优解。

设 \(R\) 为最大攻击升级次数，\(Y\) 为最大防御次数。事件表程序时间为 \(O(n+R+Y+E)\) ，空间同阶，其中 \(E=O(\sum_i\sqrt{h_i})\) .扫描上界与桶上界由输入计算，不假定它们都只到原属性上界。

参考程序采用出题人的事件表。并列的堆调度解法只保存每种敌人的下一次事件，事件存储降为 \(O(n)\) ，总空间 \(O(n+Y)\) ，代价是 \(O(\log n)\) 的事件调度。两者都通过完整范围；堆版在参考压力数据中峰值约 \(120\) MiB，事件表约 \(329\) MiB，具体计时和目标环境校准见评测记录。

图示

图对应样例二，所有价格和步长都为一。\(C\) 是总花费，\(F\) 是全部战斗的总伤害，\(H-F\) 是最后剩余生命。两种方案都花费一；蓝色方案升级后的生命更小，因而字典序更小。

数据与复现

三个样例见题面。生成配方包含十份计分输入；生成器只依赖 Python 标准库，支持 --plan、--out-dir、--case 和 --std。正式大输入及可执行文件不放入发布包。时间和内存的参考测量见性能记录。