526互联

Codeforces Round 878 (Div. 3) D. Wooden Toy Festival

发布时间 2023-06-21 19:30:45作者: 突破铁皮

题目翻译：给定一个序列，你可以把序列分为任意的三组不要求顺序，对于每一组序列给出一个数字作为标准，求出序列中和该数字的差绝对值的最大值，现在要求你选顶三个数字使得三个序列的差最大值的最大值最小

解题思路：二分，要想方差最小，就让每一组的极差都最小，即最大值减最小值最小

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2e5+10;
int n;
int a[N];
//当x取小了，则会分成大于3个序列，当x取大了则不够3个序列
bool check(int x){
	int num=1;
	int k=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]-k>x){
		num++;
		k=a[i];
	}
	}
	return num<=3;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	int l=0,r=a[n]-a[1];
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
    //奇数的话需要加一
	cout<<l/2+l%2<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
}