理 論 上 只 要 排 序 後 ， 找 出 前 K - 1 大 的 距 離 當 分 割 點 就 好 了 。

但 是 實 作 上 卻 不 能 這 麼 做 >O(n²)

那 一 個 一 個 試 距 離 ?

有 想 法 ， 但 還 是 太 慢 >O(n²)

既 然 答 案 就 在 一 個 範 圍 內 ， 那 二 分 搜 尋 法 是 個 很 好 的 選 擇 。 O(log n)


while(L<R)

L = 1 , R = ( max Service point - min Service point ) , m = ( L + R ) / 2 ;

if(solve(M)) //如 果 可 以 涵 蓋 全 部 ， 就 往 左 區 找 直 徑 ( 因 為 可 能 可 以 用 更 小 的 直 徑 )

   R=M;

else         //如 果 不 行 ， 往 右 區 找

   L=M+1;

程式碼:

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
vector<LL> point;
bool solve(int r,int N,int K)
{
    int cnt=0;
    vector<LL>::iterator it;
    for(it=point.begin();it!=point.end();)
    {
        int Range=*it+r;
        cnt++;
        if(cnt>K)
            return false;
        if(Range>=point[N-1]&&cnt<=K)
            return true;
        while(Range>=*it)
            it++;
    }
    return false;
}
int main()
{
    for(int N,K;scanf("%d %d",&N,&K)!=EOF&&N&&K;)
    {
        point.resize(N);
        for(int i=0;i<N&&scanf("%d",&point[i++]););
        sort(point.begin(),point.end());  // 排 序 ， 讓 解 決 問 題 變 得 更 簡 單

        int R=point[N-1]-point[0],L=1;
        if(K==1) {printf("%d\n",R); continue;}
        else
            while(L<R)
            {
                int M=(R+L)/2;
                if(solve(M,N,K))
                    R=M;
                else
                    L=M+1;
            }
        printf("%d\n",R);
    }
    return 0;
}

這算是使用binary search嗎?