自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:33:15，当前版本为作者最后更新于2021-08-24 22:35:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有删减，同步发表于我的博客。

麻了，自适应交互器不会写/kk，但是题目还是可以想的（

最开始想直接 std::sort 一遍，事实上这个 $<$ 没有传递性，会返回各种奇奇怪怪的结果。

事实上这是非常神仙的结论题。

结论：直接归并排序之后的数组满足 $a_i - a_{i + 1} \le 1$​。

并不知道出题人怎么想到这个神奇的性质，但知道结论后，我们不难直接递归归纳证明。

拥有这个性质的数组并不少见，因为换一种表述，初始数组为 $0\sim N-1$，然后将原数组分为若干段，每一段取反即可。

所以我们知道第 $i$ 和第 $i - 1$ 段的端点，就可以知道第 $i + 1$ 段的断点。问题转化为找到 $0$ 的位置。

由于 $0$ 只会比 $1$ 小，所以在归并时候，一直在往前跳，感性理解一下。所以排序后 $0$ 的位置在前 $\log N$ 个之内。

$\log N$ 很小，我们直接用 $N^2$ 算法求出 $0$ 的位置即可。