题目链接
题目大意
给一个长度为n的数组,问你有三个数,x,y,z,使得min(ans, max(abs(x - ai), abs(y - ai), abs(z - ai))的值是多少?
题解
这就相当于一个排完序的数组,然后分成三段,这三段分别是最集中的,然后分别求着三段的半径。最暴力的办法就是直接寻找两个中断点,但是这个时间复杂度是O(N * N) ,无法通过,那么我们可以发现,固定第一段的端点,就相当于把后一段分成两段,让这两段的最大值最小,那么办法就是二分,随着端点向右移动,左边区间的贡献值不断增大,右边的不断减小,那么他俩最相近的时候就是贡献值最小的时候。然后第一个端点的遍历时间复杂度是n,二分是logn,在这个数量级下是可以通过的。然后把这个数组分成三段,问题就转换成这三段的半径最长的最短是多少?
代码
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int a[N], n;
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (n <= 3) {
cout << "0\n";
return;
}
sort(a + 1, a + n + 1);
int ans = INT_MAX;
for (int i = 1; i <= n - 2; i++) {
if ((a[i] - a[1] + 1) / 2 >= ans)//如果目前的答案比现有的还大,没必要往下搜
continue;
int l = i + 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
ans = min(ans, (max(max(a[i] - a[1], a[mid] - a[i + 1]), a[n] - a[mid + 1]) + 1) / 2);
if ((a[mid] - a[i + 1] + 1) / 2 < (a[n] - a[mid + 1] + 1) / 2)//这个位置>=和>是没有影响的,因为我们都会向上取整
l = mid + 1;
else
r = mid;
}
}
cout << ans << endl;
}
int main()
{
IOS;
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}