我的方法是O（n）的,木有下面的二分神。
题意就是加一条权值为0的边，使得最远点距离最小.
容易证明边的起点一定是1.
那么可以枚举边的终点。
假设边的终点在点X，那么可以分2部分来计算，1-X之间的点和点X+1-N.显然后面部分中最远的点是N。
对于前面部分,距离最远的点肯定是在中间的（就是它到1的距离和到X的距离尽可能接近）,假设是Y，显然当X变大的时候,Y也会变大,只要移动一下就可以了。

#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
int n;
ll a[200010];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
ll x=-a[1];
for(int i=1;i<=n;i++)
a[i]+=x;
if(n<=2)
{
cout<<a[2]<<endl;
continue;
}
ll ans=0x7f7f7f7f;
for(int i=2;i<=n;i++)
{
ll num=0;
int pos;
if(a[i]%2==0)
pos=lower_bound(a+1,a+1+i,a[i]/2)-a;
else
pos=upper_bound(a+1,a+1+i,a[i]/2)-a;
num=max(num,a[i]-a[pos]);
num=max(num,a[pos-1]-a[1]);
num=max(num,a[n]-a[i]);
ans=min(ans,num);
}
cout<<ans<<endl;
}
return 0;
}
/*
1
4
0 7 9 100
*/

加了读入优化还跑这么慢....
这数据规模真够大的...

测试数据 #0: Accepted, time = 0 ms, mem = 2080 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 2080 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 2080 KiB, score = 10

测试数据 #3: Accepted, time = 27 ms, mem = 2076 KiB, score = 10

测试数据 #4: Accepted, time = 27 ms, mem = 2076 KiB, score = 10

测试数据 #5: Accepted, time = 35 ms, mem = 2080 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 2084 KiB, score = 10

测试数据 #7: Accepted, time = 85 ms, mem = 2076 KiB, score = 10

测试数据 #8: Accepted, time = 140 ms, mem = 2080 KiB, score = 10

测试数据 #9: Accepted, time = 195 ms, mem = 2084 KiB, score = 10

贪心证明:
假设最优方案中左边的虫洞在城市s,右边那个虫洞在城市t,则考虑城市1到城市j的距离,为
min{ d[1,j] , d[1,s]+d[t,j] }
注意不论t是多少,只要给定了t,那么d[1,j],d[t,j]都是确定的
因此不管t是什么,都要使d[1,s]尽量小.直接设s=1即可.

具体实现的时候.....
我直接去**二分距离**了.....
没有算具体的位置....
##Code

using namespace std;

ll getll()
{
ll res=0;
char c=getchar();
bool mi=false;
while( (c<'0' || c>'9') && !feof(stdin) ) mi=(c=='-'),c=getchar();
while( ('0'<=c && c<='9') && !feof(stdin) ) res=res*10+c-'0',c=getchar();
return mi ? -res : res;
}

const ll INF=(ll(1)<<56)-1;
int n;
ll a[205000];

bool able(ll dst)
{
int sec1=int(upper_bound(a,a+n,a[0]+dst)-a);
if(sec1==n) return true;
int sec2=int(upper_bound(a+sec1,a+n,a[sec1]+dst)-a);
if(sec2==n) return true;
int sec3=int(upper_bound(max((ll*)a,a+sec2-1),a+n,a[max(0,sec2-1)]+dst)-a);
if(sec3==n) return true;

return false;
}

int main()
{
int T=getint();
while(T--)
{
n=getll();
for(int i=0;i<n;i++) a[i]=getll();
a[n]=INF;

ll l=0,r=INF;
//binary search distance
while(l<r-1)
{
ll mid=(l+r)>>1;
if(able(mid)) r=mid;
else l=mid;
}
if(able(l)) r=l;
else l=r;

printf("%I64d\n",l);
}

return 0;
}

编译通过... 

├ 测试数据 01：答案正确... (0ms, 1456KB) 

├ 测试数据 02：答案正确... (0ms, 1456KB) 

├ 测试数据 03：答案正确... (147ms, 1456KB) 

├ 测试数据 04：答案正确... (188ms, 1456KB) 

├ 测试数据 05：答案正确... (145ms, 1456KB) 

├ 测试数据 06：答案正确... (179ms, 1456KB) 

├ 测试数据 07：答案正确... (649ms, 1456KB) 

├ 测试数据 08：答案正确... (645ms, 1456KB) 

├ 测试数据 09：答案正确... (471ms, 1456KB) 

├ 测试数据 10：答案正确... (933ms, 1456KB)

对于第一个虫洞必须在1号城市的证明 简单来说就是这样

设我们现在要去K城市 且虫洞入口在A 出口在B 显然A在B前会更优

那么我们一共有两种可能的方案到达那里

1. 直接走过去 路程是D[1,K]

2. 通过虫洞 路程是D[1,A]+D

这里D[X,Y]表示两城市X,Y的直线距离

那么可以注意到 第二种情况的D[1,A]并不随B点和K点的选择变化而变化

因此D[1,A]当然是取得越小越好

那么取1点就可以使得D[1,1]=0达到最小

证毕

为什么不能对第二个虫洞的位置进行二分？设起点为S（也是第一个虫洞），终点为T，第二个虫洞在X。则ans=max((a[X]-a)/2,a[T]-a[X]),可以看到前者不降，后者不增。当两者最接近的时候既是答案。这样复杂度就是(log(n))^2。

├ 测试数据 01：答案正确... (47ms, 1188KB)

├ 测试数据 02：答案正确... (16ms, 1188KB)

├ 测试数据 03：答案正确... (0ms, 1188KB)

├ 测试数据 04：答案正确... (63ms, 1188KB)

├ 测试数据 05：答案正确... (47ms, 1188KB)

├ 测试数据 06：答案正确... (16ms, 1192KB)

├ 测试数据 07：答案正确... (47ms, 1188KB)

├ 测试数据 08：答案正确... (250ms, 1188KB)

├ 测试数据 09：答案正确... (328ms, 1188KB)

├ 测试数据 10：答案正确... (546ms, 1184KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 1363ms / 1192KB

对于第一个虫洞一定要建立在一号城市的证明请参见：

http://hi.baidu.com/samroxas/item/9b403a21eb94339cb73263d9

证明可能有误，发现请指出并留言，非常感谢。

题目允许我们放两个虫洞，可以发现其中一个放在1号点上一定可以出现最优解，

就不证明了。那么接下来就可以二分1到其他点的最小距离的最大值，验证的方法就是

加入另一个个虫洞能否满足......具体看代码的check部分

program T1;

var i,j,k,l,n,m,min,max,mid,t:longint;

a,d:array[1..300000] of longint;

function check(mid:longint):boolean;

var i,j,k:longint;

begin

for i:=1 to n do

if d[i]>mid then

begin

for j:=i to n+1 do

if d[j]-d[i]>mid then break;

for k:=j to n do

begin

if d[k]-d[j-1]>mid then exit(false);

end;

exit(true);

end;

end;

procedure main;

begin

while minmax do

begin

mid:=(min+max) div 2;

if check(mid) then max:=mid else min:=mid+1;

end;

writeln(min);

end;

procedure init;

var i:longint;

begin

read(t);

for i:=1 to t do

begin

fillchar(d,sizeof(d),0);

fillchar(a,sizeof(a),0);

read(n);read(a[1]);d[1]:=0;

for j:=2 to n do

begin

read(a[j]);

d[j]:=a[j]-a[1];

end;

min:=0;max:=d[n];

main;

end;

end;

begin

init;

end.

├ 测试数据 01：答案正确... (0ms, 1192KB) 

├ 测试数据 02：答案正确... (47ms, 1192KB) 

├ 测试数据 03：答案正确... (0ms, 1192KB) 

├ 测试数据 04：答案正确... (16ms, 1188KB) 

├ 测试数据 05：答案正确... (16ms, 1188KB) 

├ 测试数据 06：答案正确... (63ms, 1188KB) 

├ 测试数据 07：答案正确... (47ms, 1188KB) 

├ 测试数据 08：答案正确... (250ms, 1188KB) 

├ 测试数据 09：答案正确... (281ms, 1188KB) 

├ 测试数据 10：答案正确... (624ms, 1184KB) 

var

x:array[-1..200000]of longint;

ca,num,ans,u,i,n:longint;

function min(x,y:longint):longint;

begin

if x

当心：x可能是负数！！！！

我的读入优化函数没有考虑负号问题！！白白t了5次！！！