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

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

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

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

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

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