[TIOJ 1805] 全點對最短路徑

又被雷了QQ，這題的一大盲點是「蟲洞可以不用架在城鎮上」！！！！！
我卡了很久只想到O(n^3)解，問人才知道可以不用在城鎮上......
這樣問題就變簡單了，不過好像還是沒有簡單到哪裡去(吧(?)

作法：

重洞可以不用架在城鎮上的話，二分答案就可行了，所以對於一個 d ，我們要判斷是否能夠找到兩個點，在這兩個點建蟲洞之後可以讓任兩點的最短距離都<=d。所以我們需要先知道蟲洞應該要架在哪是最好的。

假設蟲洞的左端點建在A，右端點建在B，所有城鎮的最左城鎮叫P，最右城鎮叫Q，那麼如果 AP + BQ < d ，就可以把 A 往右移，B 往左移，移到 AP + BQ = d 為止，而且他們移動的距離一樣(也就是保持AB的中點固定，然後讓A根B往內縮)，可以證明調整之後的任兩點之間的最短距離都不會變大，還有機會變小，所以這樣是可行的。

設AP = x ， BQ = y ，假設 x <= y ( 如果 y <= x 等等可以推出一樣的結果 ) ，那麼可以得到在AB中間的某個點 Z ，如果想要讓他到P和Q的最短距離都<=d 的話，那必須要滿足 AZ <= x 或是BZ<=x ，所以可以知道 x 越大越好，但又不能超過 y ，且他們加起來 = d ，所以取 d/2 是最好的，也就是兩個重洞分別建在離 P 的 d/2 處和離 Q 的 d/2 處。

而做到了這個結論後也可以不用二分答案了，直接用 lowerbound 就可以得到答案了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=4000+10 ;
int a[maxn] ;
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n ; scanf("%d",&n) ;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
        if(n==2) { printf("0\n") ; continue ; }
        sort(a+1,a+n+1) ;
        int x=lower_bound(a+1,a+n+1,(a[1]+a[n]+1)/2)-a ;
        int ans=-1 ;
        if(x!=n+1) ans=max(ans,a[n]-a[x]) ;
        if(x!=1) ans=max(ans,a[x-1]-a[1]) ;
        printf("%d\n",ans) ;
    }
}