题解：CF2187A Restricted Sorting

yimuhua · 2026-08-09 17:10:17 · 题解

特判已经排序。先设 k 为常数，若 (x,y),(y,z) 均可交换则可以三次交换 (x,z)。

那么我们要求出连通块，考虑什么时候 x,y 连通。显然 mn 与 mx 必须连通。\ge mn+k 的数均与 mn 连通，\le mx-k 的数均与 mx 连通。

所以连通块即所有 \ge mn+k\lor\le mx-k 的数均连通、其余为孤点。除了排序后位置不变的数显然都必须交换，那么 k 取这些数到 mx,mn 距离的 \max 的最小值即可。

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int t, n, a[200005], b[200005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i], b[i] = a[i];
        sort(b + 1, b + n + 1);
        int mn = b[1], mx = b[n], k = inf;
        for(int i = 1; i <= n; i++)
            if(a[i] ^ b[i])
                k = min(k, max(mx - a[i], a[i] - mn));
        cout << (k < inf ? k : -1) << '\n';
    }
    return 0;
}