CF-1077-C. Restricted Sorting（当发现一个条件取决于两个数字的时候，可以想想，是不是可以只取决于一个数字？）

题目大意

给定长度为$n$的数组$a$。对于整数$k$，我们称其为piggy，当且仅当通过执行以下操作任意次数（可能为零），可以将$a$以非递减顺序排序：

• 首先，选择两个索引$i$和$j$（$1 \le i < j \le n$），使得$|a_i - a_j| \ge k$;

• 然后，交换$a_i$和$a_j$。

您需要确定最大的piggy整数$k$。如果不存在这样的整数，则输出$-1$。

思路讲解

不难注意到，我们可以选用最大的数字或者最小的数字去做中转站，

乍一看，好像选择最小的数字，还是选择最大的数字，取决于两个数字 $to$ 和 $now$？实际上不是的，我们完全可以换着来，比如说：

这样子就实现了 $to$ 用 $mn$，$now$ 用这个 $mx$，反之亦然，完全可以只根据一个数去选择。

okay，那就行了。我们发现，这个 $to$ 和 $now$ 一定都是和有序序列中的同位置值不一样的点，因此，我们的答案其实就是：（其中 $S$ 为所有和有序序列中的同位置值不一样的点的下标集合）

$$ans\gets\min_{i\in S}(\max(mx-a_i,a_i-mn))$$

当然，也可以使用代码中的这个贪心实现。

AC代码

AC
https://codeforces.com/contest/2188/submission/360594620

源代码

/**
 * Problem: C. Restricted Sorting
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/C
 * Created: 2026-01-30 00:31:10
 * Author: Gospel_rock
 */

#include <iostream>
#include <numeric>
#include <algorithm>
#include <complex>
#include <map>
#include <ranges>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <chrono>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    if (is_sorted(all(A))) {
        cout<<-1<<"\n";
        return;
    }
    vector<ll> a_sort(all(A));
    sort(all(A));
    ll mn=*min_element(all(A)),mx=*max_element(all(A));
    auto check=[&](ll k) {
        for (int i=0;i<N;++i) {
            if (A[i]==a_sort[i]) {
                continue;
            }
            if (abs(A[i]-mn)<k && abs(mx-A[i])<k) {
                return false;
            }
        }
        return true;
    };
    ll l=0,r=mx;
    while (l<r) {
        ll mid=(l+r+1)>>1;
        if (check(mid)) {
            l=mid;
        }else {
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*

*/

心路历程（WA，TLE，MLE……）