题意：给一个数列（整数），用一些不相交的区间去覆盖（只能是用端点去覆盖，端点可以交）。而且区间出度相等。求最大区间长度。
开始一下就敲了，枚举每个区间长度，判断合法，更新最大。但是后来一看小数，感觉不行，改为二分，后来还是挂了。。。
赛后才知道，二分的时候，答案必需要满足单调性啊，这里小的数据不行，大的数据可以行！如 0 1 5 6 10， 3不行，4行。
后来才知道，枚举时，每个差值的一半也是可以的：仔细想想很容易证明。（水，坑）
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int>v; int n;
bool ok(double tmax)
{
int fl=-1;
for(int j=1;j<n-1;j++)
{
if(fl==-1) //之前的放在前
{
if(v[j]-tmax<v[j-1]) //放前面不行，放后面：
{
if(v[j]+tmax<=v[j+1]) //放后面
{
fl=1;
if(v[j]+tmax==v[j+1]) //下一个免了
{
j++;
fl=-1;
}
}
else //否则不行
return 0;
}
else //放前面
fl=-1;
}
else //之前的在后面，
{
if(v[j]-tmax<v[j-1]+tmax) //放前面放不来
{
if(v[j]+tmax<=v[j+1])
{
fl=1;
if(v[j]+tmax==v[j+1])
{
j++;
fl=-1;
}
}
else
{
return 0;
}
}
else
{
fl=-1;
}
}
}
return 1;
}
vector<double>dis;
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
int tx=0;
v.clear();
dis.clear();
for(int i=0;i<n;i++)
{
cin>>tx;
v.push_back(tx);
}
sort(v.begin(),v.end());
for(int i=0;i<n-1;i++)
{
double d=v[i+1]-v[i];
dis.push_back(d);
dis.push_back(d/2.0);
}
sort(dis.begin(),dis.end());
for(int i=dis.size()-1;i>=0;i--)
{
if(ok(dis[i]))
{
printf("%.3lf
",dis[i]);
break;
}
}
}
return 0;
}