[JOI Open 2021] Monster Game

7KByte · 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 个之内。