Statement
\(T\) 组评测，每组数据给定长度 \(n\) 与长度为 \(n\) 的序列 \(a\)，你需要选三个数 \(x,y,z\)，输出可得到的最小的 \(\max\{\min\{|a_i-x|,|a_i-y|,|a_i-z|\}\}\)。
Solution
如果只要我们选一个数，显然我们要选中位数。
如果只要我们选两个数，排序后将序列下标分为 \([0, \mathrm{index})\) 和 \([\mathrm{index}, n)\)，分别选两个区间的中位数。
问题是要选三个数，不能朴素地枚举分界的下标。
发现对于某个答案的值，比它大的答案也是存在的，即答案在值域上连续，且有单调性。
二分答案 \(s\)，考虑对一个 \(s\)，从小到大覆盖整个序列。
保证 \(a\) 有序后，第一次选择 \(a_0 + s\) 最大能够覆盖到 \([a_0, a_0 + 2s]\)。
假设 \(a_i\) 是第一个大于 \(a_0 + 2s\) 的数，第二次选择 \(a_i + s\) 最大能够覆盖到 \([a_i, a_i + 2s]\)。
最后假设 \(a_j\) 是第一个大于 \(a_i + 2s\) 的数，剩下的区间即为 \([a_j, a_{n-1}]\)，判断能否被选完（\(a_{n-1} - a_j + 1 \le 2s\) 是否成立）即可。
不难证明该策略最优，因此我们能在 \(\mathcal{O}(\log^2{(\max a - \min a)})\) 的时间内处理单个询问。
Code
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int& i : a) std::cin >> i;
std::sort(a.begin(), a.end());
int l = 0, r = a[n - 1] - a[0];
while (l < r) {
int mid = (l + r) / 2;
int pos = std::upper_bound(a.begin(), a.end(), a[0] + 2 * mid) - a.begin();
pos = std::upper_bound(a.begin() + pos, a.end(), a[pos] + 2 * mid) - a.begin();
if (pos == n || a[n - 1] - a[pos] <= 2 * mid) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << l << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt;
std::cin >> tt;
while (tt--) solve();
return 0;
}