嗨嗨嗨蓝 劣又来更新了，今天送你们一个程序模板！ //[蓝 劣]的程序模板，制作不易！：包括变量、数组、队列、结构体、模数、输入、输出、循环、二分函数、dfs深搜函数、sort比较函数、判断、无返还函数、无返还函数调用、三种实用头文件! #include<bits/stdc++.h> #include #include using namespace std; #define MOD 998244353 int n,m; int a,b; int res=0,sum=0; int x[10005],y[10005]; queue<pair>p; struct node{ int u; int v; int w; string s; }o[50]; void dfs(int max,int h){ if(){

}

} bool cmp(int o1,int o2){ if(){ return ; }else{ return ; } } int find(int q){ int r=0,int l=0; while(a[mid]<=r){

}

} int main(){ p.front(); p.pop(); cin>>; for(int i=1;i<= ;i++){

}
for(int i=1;i<= ;i++){
	
}
for(int i=1;i<= ;i++){
	
}
while(){
	
}
while(!){
	
}
sort(+n,+1+n,cmp);
dfs(1,0);
printf();
cout<<;
cout<<" ";
for(int j=1;j<= ;j++){
	cout<<;
}

return 0;

}

木雕玩具

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

显然答案 $k$ 具有可二分性。也就是说，当 $k < k_0$ 时一定不存在合法的 $x, y, z$，当 $k \geq 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$ 都被覆盖了，那么就合法，否则不合法。

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

#define int long long
#define endl '\n'
using namespace std;
int n,a[1000000];
bool check(int x){
	int i=0,u=0;
	while(i<n&&u<3){
		int l=a[i]+2ll*x;
		u++;
		while(i<n&&a[i]<=l)i++;
	}
	return i==n;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int l=0,r=a[n-1]-a[0];
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	return 0;
}