[ARC196A] Adjacent Delete 题解

假设 $n$ 是偶数。如果我们忽略删除相邻数的条件，即可以任选两个数相减，那么答案应该是前 $\frac{n}{2}$ 大的数（记作“较大数”）的和减去前 $\frac{n}{2}$ 小的数（记作“较小数”）的和。

容易发现，当我们只能选相邻的数相减时，依然可以达到这个答案，因为在任意时刻，总存在至少一对较大数与较小数相邻。

当 $n$ 是奇数，那么一定有一个元素不被选，且这个元素一定在奇数位，这样才能把数组分成长度为偶数的两段。枚举不被选的位置，用对顶堆维护前后两段的答案即可。

时间复杂度 $O(n\log n)$。

提交记录