题解 CF1840D【Wooden Toy Festival】

不妨设 \(a\) 单调递增（无重复），显然如果 \(n\le 3\) 答案就是 \(0\)。

显然答案 \(k\) 具有可二分性。也就是说，当 \(k < k_0\) 时一定不存在合法的 \(x,y,z\)，当 \(k\ge k_0\) 时一定存在，\(k_0\) 就是答案。

因此二分答案，只需要验证答案 \(k\) 是否存在合法的 \(x,y,z\)。

为了覆盖到 \(a_1\)，且 \(x\) 尽量往大取（这样可以覆盖更多的 \(a_i\)），我们令 \(x=a_1+k\)。接下来一段区间的 \(a_i\) 会被 \([x-k,x+k]\) 覆盖，我们跳过这段区间，找到下一个未被覆盖的 \(a_i\)。类似于刚刚的思路，我们令 \(y=a_i+k\)，再找到下一个未被覆盖的 \(a_j\)，令 \(z=a_j+k\)。如果此时所有 \(a_i\) 都被覆盖了，那么就合法，否则不合法。

时间复杂度 \(\mathcal O(n\log w)\)，其中 \(w\) 为值域。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
    uniform_int_distribution<ll> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 2e5+5, inf = numeric_limits<ll>::max();

ll T, n, a[N];

bool check(ll M) {
    ll x = a[1] + M, y = inf, z = inf;
    rep(i, 1, n) {
        if(abs(a[i] - x) <= M);
        else if(y == inf) y = a[i] + M;
        else if(abs(a[i] - y) <= M);
        else if(z == inf) z = a[i] + M;
        else if(abs(a[i] - z) <= M);
        else return false;
    }
    return true;
}

int main() {
    for(scanf("%lld", &T); T; T--) {
        scanf("%lld", &n);
        rep(i, 1, n) scanf("%lld", &a[i]);
        sort(a+1, a+1+n);
        n = unique(a+1, a+1+n) - a - 1;
        if(n <= 3) {puts("0"); continue;}
        ll L = 0, R = a[n] - a[1] + 1;
        while(L < R) {
            ll M = (L + R) >> 1;
            if(check(M)) R = M;
            else L = M + 1;
        }
        printf("%lld\n", L);
    }
    return 0;
}