1840D - Wooden Toy Festival - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long LL;
typedef pair<int,int> PII;
int a[N];
int n;
//二分查找最小的区间最大值和最小值的差能使整个区间分为3份

bool check(int x){
    int cnt=0,now=0;
    for(int i=0;i<n;i++){
        if(ceil((a[i]-a[now])*1.0/2)>x){
            cnt++;
            now=i;
        }
    }
    if(cnt<=2)return true;
    else return false;
}

void solve(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
}