题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4932

题目大意：

来自百度翻译
在X轴上有N个点。苗苗想用同样长度的片段来覆盖它们。
有两个限制：
1.如果有一个线段T，则该点是T的左端或右端。
2.任意两段相交的长度等于零。
例如，点2由[2，4]转换而不是由[1，3]转换。[1,2]和[2,3]是合法段，[1,2]和[3,4]是合法段，但[1,3]和[2,4]不是（相交长度不等于零），[1,3]和[3,4]不是（长度不同）。
苗苗想最大化分段长度，请告诉她最大分段长度。
据你所知，这一点不可能碰巧在同一位置。

解题思路

我的思路是二分区间长度判断是否可行，但是wa了。
正确思路：
枚举区间长度，区间长度不是两个相邻位置的差值就是差值的一半，这步是核心之一。
判断是否可行。
判断的时候还要注意一点：
存在一个区间覆盖两个点的情况，比如：-100 32 45 4 12 231

AC代码

#include<bits/stdc++.h>
#define ll long long
const int N=100;
const int inf=0x3f3f3f3f;
const double esp=1e-8;
using namespace std;
int T,n;
double a[N];
vector<double> sub,tmp;
bool check(double x,vector<double> v)
{
    for(int i=0;i<v.size()-1;i++)
    {
        if(v[i]==0) //特判一个区间覆盖两个点
        {
            continue;
        }
        else if(v[i]<x)//i点与i-1点之间的距离已经不足以容纳x
        {
            if(v[i+1]<x) return false;//判断i点与i+1点之间的距离是否足以容纳x，若否，false
            v[i+1]-=x;//若是，i点与i+1点之间的可容纳范围减少x
        }
        else
        {
            v[i]-=x;//可有可无，不影响答案//含义为把x塞到i点与i-1点之间
        }
    }
    return true;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        sub.clear();
        tmp.clear();
        for(int i=2;i<=n;i++)
        {
            tmp.push_back(a[i]-a[i-1]);//用于存储两点之间的距离
            sub.push_back(a[i]-a[i-1]);
            sub.push_back((a[i]-a[i-1])/2);//用于存储所有的区间长度可能
        }

        sort(sub.begin(),sub.end());
        for(int i=sub.size()-1;i>=0;i--)
        {
            if(check(sub[i],tmp))
            {
                printf("%.3lf\n",sub[i]);
                break;
            }
        }        
    }
}