P4597 序列 sequence

· · 题解

尝试给出一个比较严谨的贪心证明。

序列的最终状态一定是若干连续段，并且每个连续段的值是单调增的。

对于每个段，我们都有方法可以调整到最终状态的花费并使得最优。比如先对段内元素进行排序，然后从两端不断抽出元素，把它们差的绝对值累加，当剩余元素不足 2 个时停止。

这种方案的正确性容易证明：由绝对值的几何意义可知，线段上两点到它们之间任意一点的距离相同，所以只需要从外到内累加，它们的中位数一定能被取到，总数为偶数时取较小值作为中位数。

于是可以定义一个“中和” 操作：取一个二元组 \left ( a,b \right )，满足 b<a，把他们同时调整为 \left [ b,a \right ] 之间的任意整数 c，花费为 a-b。

由于最终每段互相独立且中位数单调递增，所以一定能通过“中和” 操作取到最优解。

但是仍有部分限制：“中和” 操作所选的数不能有重复，因为这相当于把三个数都限定为它们的中位数。比如取了 \left ( a,b \right ) 和 \left ( b,c \right )，由于 b 同时属于 \left [ b,a \right ] 和 \left [ c,b \right ]，所以 a,b,c 都只能取值为 b。

但稍作观察即可发现，只对 \left ( a,c \right ) 进行“中和” 操作即可达到更优的效果，不妨将其命名为“改接”。

尝试动态维护最优序列，若加入新数仍满足单调不降，那么把它作为一个自由元加入大根堆，若加入后不满足，就用“中和” 操作处理，花费为堆顶元素与其的差，弹出堆顶，并将这个数加入大根堆两次。

为什么是两次？原因很简单：如果想把这个数作为大数再与更小的数进行“中和” 操作，首先要通过“改接”，使其变成自由元，同时补上少的那部分花费，下一次才能用它进行“中和”。

这时大根堆中元素有两种类型：自由元和待“改接” 的元素。自由元的值就是它本身，而待“改接” 元素的存在说明这个元素（不妨设为 x）与一个更大的数 y 进行了“中和”，那么这两个数的值域为 \left [ x,y \right ]，又因为要使最大值尽可能小，所以当前序列的最大值就是堆顶元素的值。

容易发现每次操作的代价一定是最少的，现在只需证明能通过这样操作得到合法序列。

加入后满足单调不降显然合法，只需证明加入后不满足仍成立，设堆顶元素值为 d。

如果堆顶是自由元，直接“中和” 即可，因为两数仍然能取到 d，所以一定合法。

如果堆顶元素要进行“改接”，由于“改接” 前较大值的取值已经限定为 d 了，那么从它开始到末尾的所有值只能为 d，“改接” 后值域扩大，一定还能取到 d，并且新增自由元的值也是 d，所以合法。

纵上，处理完新元素后序列仍合法，同时因为每不操作一定最优且可以只用“中和” 操作得到最优解，所以该算法正确。

代码已经有很多了，这里就不粘了。