菜王的 blog

出题人题解。

首先有一个转化是我们可以求出最终的集合 $S$，再倒过来进行交换操作得到初始的 $S$。

然后考虑如果获得了一个数 $p$ 之后，你可以把它和 $1$ 交换。因为 $p$ 是所有 pair 中更大值最小的，所以一定有 $p \le o$，其中 $o$ 是与 $1$ 配对的数。

先不考虑 $p = o$ 即 $p$ 与 $1$ 配对的情况，此时有 $p < o$。

那么和 $1$ 交换之前，配对情况显然是 $(q, p), (1, o)$，交换之后配对情况变为 $(1, q), (p, o)$，且有 $q < p < o$，则操作后返回的 $res$ 一定为 $q$。于是我们知道了，在这次操作前 $p, q$ 是配对的，但是这并没有什么用，因为无法确保 $p, q$ 之前没有动过，也无法确保以后不会动。

我们还要找到一个更大的数与 $q$ 配对从而将它覆盖在底下来得到新的 $res$，选择 $2n$ 就可以了。于是交换 $1, 2n$，配对情况变为 $(q, 2n), (p, o)$（如果 $o = 2n$ 则变为 $(q, 2n), (1, p)$，但这并不重要），于是我们成功把 $q$ 覆盖在了底下。而且因为 $2n$ 是全局最大值，只要 $q, 2n$ 这两个数保持配对，那么它们就都不会成为 $res$，可以直接将这两个数删掉，变为一个 $n' = n - 1$ 的子问题。

现在考虑 $p = o$ 的情况。如果是这种情况，交换 $1, p$ 实际上不会产生任何效果，可以通过返回的 $res$ 是否变化来判断。然后我们只需要同样地交换 $1, 2n$ 来覆盖住 $p$ 即可。

最后 $n = 1$ 的时候一定会剩下一个 $1$，而另外一个数就是 $res$，共需要 $2(n - 1)$ 次询问。但是这个 $res$ 是我们能通过之前产生的 pair 推导得出的，所以就可以减少一次询问，做到 $\max(0, 2n - 3)$ 次询问。

code