3 3 1 2 3 3 1 2 4 4 1 9 100 10
1.000 2.000 8.000HintFor the first sample , a legal answer is [1,2] [2,3] so the length is 1. For the second sample , a legal answer is [-1,1] [2,4] so the answer is 2. For the thired sample , a legal answer is [-7,1] , [1,9] , [10,18] , [100,108] so the answer is 8.
比赛时用二分做的，后来被hack掉了。。
二分结果不对：比如下面这组数据：
4
0 1 4 5
所有可能的线段长度最大可能有两种情况（某两个相邻点之间的距离，某两个相邻点之间的距离的一半）。为什么说是最大，比两个相邻点之间的距离一半小当然没问题。所以我们就把所有相邻的点之间的区间距离以及它的一半保存在数组里面，从小到大排序，逆向遍历，每遍历一个数判断是否符合题意，如果符合，就退出，得到了答案。怎么判断是否符合题意呢？
用到了贪心的思想，能放左边，放左边，不能放左边，放右边。
注意到本题并没有对线段的多少有限制，只要求线段的最大长度，我觉得这个条件对贪心起着关键作用。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
int num[60];
double inter[120];//区间，里面保留着相邻两个点的区间距离以及区间距离的一半
const int eps=1e-6;
int n;
bool ok(double l)
{
double temp=num[1];
for(int i=2;i<=n-1;i++)
{
if(temp==num[i])//当倒数第二个点正好被覆盖时，不用计算后面tep=num[i]+l if(temp>num[i+1]) 最后那个点是自由的
continue;
if(num[i]-l>=temp)
temp=num[i];
else
{
temp=num[i]+l;
if(temp>num[i+1])
return false;
}
}
return true;
}
int main()
{
int t;cin>>t;
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+1+n);
int cnt=0;
for(int i=1;i<=n;i++)
{
inter[cnt++]=num[i]-num[i-1];
inter[cnt++]=(num[i]-num[i-1])/2.0;
}
sort(inter,inter+cnt);
double ans=0;
for(int i=cnt-1;i>=0;i--)
{
if(ok(inter[i]))
{
ans=inter[i];
break;
}
}
cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans<<endl;
}
return 0;
}
[BestCoder Round #4] hdu 4932 Miaomiao's Geometry （贪心）,布布扣,bubuko.com
[BestCoder Round #4] hdu 4932 Miaomiao's Geometry （贪心）
原文：http://blog.csdn.net/sr_19930829/article/details/38487617