#15706: 理論與實作


qqrainbow (愛蜜莉雅)

School : 國立嘉義高級中學
ID : 83319
IP address : [140.113.240.62]
Last Login :
2022-04-17 14:14:39
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [36.239.64.89] | Post Date : 2018-10-21 19:21

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

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

那 一 個 一 個 試 距 離 ?

有 想 法 , 但 還 是 太 慢 >O(n2)

既 然 答 案 就 在 一 個 範 圍 內 , 那 二 分 搜 尋 法 是 個 很 好 的 選 擇 。 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;
}
 
#25142: Re:理論與實作


hsugoya@gmail.com (Мигает cf4?)

School : 國立臺北科技大學
ID : 139476
IP address : [36.224.220.87]
Last Login :
2022-03-10 23:09:35
c575. APCS 2017-0304-4基地台 -- 2017年3月APCS | From: [36.224.220.95] | Post Date : 2021-04-23 19:37

這算是使用binary search嗎?

 
ZeroJudge Forum