CF-2187A-Restricted Sorting

题目

2187A Restricted Sorting

题目意思

现在有一个数组 $a$ ，要将它通过元素交换排序成一个非降序的数组，要求是每次交换的两个元素满足 $|a_i - a_j| \ge k$ 也就是选差值至少为 $k$ 的两个元素。

求最大的 $k$ 。如果没有，输出 $-1$ 。

思路

错误思路

先得到排序之后的正确的数组 $b$ ，

找对应位置上不一样的 $a[i]$ 和 $b[i]$，求最大/最小的 $abs(a[i] - b[i])$ 。
找出所有不在对应位置上的数字，组合到一个集合里，对集合排序，求排序后相邻元素差值的最大/最小值。

这都是不对的。原因分别是：

没有考虑到元素到该去的位置可以“辗转腾挪”。
只考虑了错误位置的元素组成的“小圈子”，但事实上，它们可以通过“圈子”外的元素作为中转去到该去的位置，而那样的结果可能更优。

正确思路

假设现在 $x$ 不在正确的位置上，需要和别的数 $y$ 交换。

根据条件，$|x-y| \ge k$ 的时候才能交换，当 $k$ 非常小的时候，能交换的 $y$ 可以有很多选择，而我们希望 $k$ 尽可能大，那 $k$ 最大能是多少呢？

应该是 $k= d_1 = max(x - mn, mx - x)$ ，这个时候，$x$ 还能喝最大值或最小值交换，若 $k$ 再大，$x$ 就不可能被交换了。

因此 $k \le d_1$ ，这样 $x$ 才有机会去到正确的位置。

对于 $y$ 同理，可以得到 $k \le d_2 = max(y - mn, mx- y)$ 。

综合起来，$k \le min(d_1, d_2)$ 。

假设 $d_0 = |x-y|$ ，那么 $d_0$ 一定不超过 $d_1$ 和 $d_2$ 。

假设 $d_2 \lt d_1$ ， $k = min(d_1, d_2) = d_2$ ，$y$ 可以交换最大或最小值，$x$ 也能，所以 $x$ 和 $y$ 可以通过最大或最小值来交换，而这种情况下的 $k$ 会优于直接 $x$ 和 $y$ 交换。

最终，对所有不在正确位置上的值 $x$ 求 $d=max(x - mn, mx - x)$ ， $k$ 等于最小的 $d$ 。

特殊情况，数组已经符合要求，输出 $-1$ 。

我写的太不清楚了，让 deepseek 来

错误思路的“死穴”
先把数组排序得到目标数组 b，然后：

看 abs(a[i] - b[i])
比如 a = [10, 1, 5]，b = [1, 5, 10]。
位置 0 的 10 和 1 差 9，位置 1 的 1 和 5 差 4。
但真正的答案并不是 9 或 4，因为元素不是非要“一步到位”地跳到自己的目标位置，它完全可以先跟最大值/最小值交换，再辗转到位。
核心错误：交换条件是“任意两个元素的差值”，不是“这个元素和它最终位置的差值”。

只看“错位元素”内部的关系
比如 a = [1, 5, 6, 2]，错位的是 {5, 6, 2}。
它们内部差值很小，但真正的答案却是 4，因为元素 5 可以借助全局最小值 1（距离 4）来移动。
核心错误：忽略了全局最大值和最小值可以作为“万能中转站”，让错位元素越过内部的小圈子。

正确思路：从“让 k 最大”出发
我们要找一个最大的 k，让所有错位元素都能动起来。

关键观察：
对于一个元素 x，数组中离它最远的元素，一定是全局最小值 mn 或全局最大值 mx。
它到这两个端点的最大距离是：
$d = \max(x - mn,\; mx - x)$
如果 k > d，那么 x 和数组中的任何一个元素的差值都小于 k，它连第一次交换都做不了，直接“冻住”。
所以，为了让 x 至少能迈出第一步，必须满足：
$k \le d$
为什么取所有 d 的最小值？
因为 k 是全局统一的，必须同时照顾到所有错位元素。
只要有一个错位元素的 d 很小，k 超过它就会导致全盘失败。
这就是经典的“木桶效应”——最短的那块板决定了上限。

因此：

答案 = 所有错位元素的 d 中的最小值

额外补充（便于理解）

为什么“能碰到端点”就一定能排序？
因为最大值和最小值可以当作两个“临时空位”，通过它们做中转，可以把任意元素放到任意位置（这是这类交换问题的常用构造结论，无需在代码中实现，只用于证明可行性）。

如果数组已经有序：
不需要任何操作，k 可以无限大，所以输出 -1。

😊

代码

T = int(input())
for _ in range(T):
    n = int(input())
    nums = list(map(int, input().split()))
    order = sorted(nums)
    mn, mx = order[0], order[-1]
    ans = 0x3f3f3f3f
    for x, y in zip(nums, order):
        if x != y:
            ans = min(ans, max(x - mn, mx - x))
    print(ans if ans != 0x3f3f3f3f else -1)