p3470 sol（POI2008 BBB）

AllenJYL · 2024-12-19 13:02:51 · 题解

注意到最优解一定是先执行若干次操作 2 再执行操作 1，可以通过调整法证明。

考虑没有操作 2 时的情况。我们需要满足两个条件：

根据条件 2，我们可以轻松算出最终情况有多少 1/-1。

根据条件 1，定义 mn=\min(s_i)，考虑到修改靠前的 -1 至 1 更优，我们又不得不至少将前 \lceil\frac{\max(0,-p-mn)}{2}\rceil 个减号修改为加号。

所以总修改数就是条件 1 的修改数加上处理完条件 1 后条件 2 的修改数。需要注意的是，处理完条件 1 后我们知道了当时的 1/-1 数，需要与条件 2 算出来的期望值做差。

对于 1 改为 -1 的情况，一定是修改靠后的位置；对于 -1 改为 1 的情况，一定是修改靠前的位置。

有了操作 2，只需要动态维护 mn 即可。