自动搬运

查看原文

来自洛谷，原作者为

	vzcx_host vzcx 系列第一站

搬运于2025-08-24 22:53:25，当前版本为作者最后更新于2023-12-20 20:20:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不会严格证明结论，但是过了。

考虑到当 $x$ 后面紧跟 $x+1$ 时这两个数完全可以绑在一起，因此我们考虑将 $i$ 归位时尽可能增加绑定数对的数量。

假定 $1\sim i-1$ 已经归位，考虑将 $i$ 归位，如果 $i$ 已经在位置上了可以直接跳过，否则 $i$ 的位置必然为第二个区间的左端点，这时候考虑另外三个点选哪里，若 $i+1$ 在 $i$ 的左边，我们可以将 $i-1,i+1$ 中间的数与 $i$ 交换（若 $i-1$ 紧贴 $i+1$，则第一个区间取 $i+1$ 的位置到 $i$ 的位置减一），$i$ 归位的同时 $i$ 与 $i+1$ 绑定；若 $i+1$ 在 $i$ 的右边，将第二个区间的右端点更新为 $i+1$ 的位置，继续考虑 $i+2$ 的位置，直到找到一个数在 $i$ 左侧。若 $j$ 为找到的第一个在 $i$ 左侧的数，则操作后 $i$ 会归位，$j-1$ 会与 $j$ 贴合。由于操作前 $i$ 没有归位，其左侧必定有别的数。

猜为什么这样是对的：将 $i,j,j+1$ 的位置视为“墙”，“墙”把原序列分为了四段，每段段内的相对顺序没变，意味着其它优化位置没有被破坏，看起来很对。