题解

思路

若要在第 $k_i$ 秒造成至少 $h_i$ 点伤害，最省的方式一定包含连续施法区间

其伤害依次为 $1,2,\ldots,h_i$。多个需求区间若相交，就必须合并成一个更长的连续施法区间；互不相交的区间之间可以把伤害重置为 $1$。

长度为 $x$ 的连续区间耗费

做法

按出现时刻从后向前扫描。维护当前合并段的左右端点 $[L,R]$。对于怪物 $i$，令 $S=k_i-h_i+1$：

• 若 $k_i\ge L$，它与当前段相交，令 $L=\min(L,S)$；
• 否则，结算当前段的三角数，并新建区间 $[S,k_i]$。

扫描结束后再结算最后一段。

极小时间轴子任务可以逐秒维护“上一秒伤害”并枚举不施法、重置为 $1$、增加为 $x+1$ 三种动作。若所有需求区间互不相交，则直接把每个 $h_i$ 的三角数相加。

正确性证明

任一怪物的最后 $h_i$ 次连续递增伤害构成区间 $[k_i-h_i+1,k_i]$，因此任何合法方案都必须覆盖所有这些区间。

相交区间不能用一次伤害重置分开，否则共同覆盖部分之后无法在两个终点同时达到所需伤害；把它们合并为一个连续递增段恰能满足全部需求。互不相交的合并段之间重置伤害只会减少法力，因此各段独立取从 $1$ 开始的递增序列最优。

算法准确求出所有需求区间的并集连通段，并对每段加入其最小三角数代价，故总和就是全局最小法力。

复杂度分析

每个测试用例时间复杂度为 $O(n)$，空间复杂度为 $O(1)$（不计输入数组）。