题解：P11467 网瘾竞赛篇之 generals 大法好

· · 题解

这里是官方题解。

因为占领每个城堡所产生的收益是相同的，所以最优情况下一定是按照 a_i 从小到大的顺序占领城堡。

假设最终兵力超过对方时，t1e 已经额外占领了 p 座城堡，那么这 p 座城堡一定是越早占领，产生的收益越多。

有了以上两个结论，我们可以先将 a_i 从小到大排序，设 f_i 代表额外占领 i 座城堡所需要的最小回合数，g_i 代表额外占领第 i 座城堡时剩余的总兵力，那么可以推出如下的状态转移方程：

\begin{aligned} f_{i} &= f_{i - 1} + \max\left(0, \left\lceil\frac{a_{i} - g_{i - 1}}{x + i - 1}\right\rceil\right) + 1 \\ g_{i} &= g_{i - 1} + (x + i - 1) \times \left\lceil\frac{a_{i} - g_{i - 1}}{x + i - 1}\right\rceil - a_i \end{aligned}

对于所有 i，求出额外占领 i 座城堡后，总兵力超过对方所需要的最小总回合数，求最小值即为答案。

需要额外判断，如果将所有城堡全部占领后，兵力增长速度仍然不比对手快，即 x + n \le y 时，兵力永远不会超过对方。