2023.1.15 PM 10:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=c575 出題者 : 2017年3月APCS 標籤 : 二分搜尋法 難易度 : 3
解題想法 : 首先可以確定一件事情,就是假如所有基地台的直徑為m時,能夠覆蓋所有服務點的話,那麼比m大的所有直徑長都必能夠覆蓋所有服務點,反之,若無法覆蓋所有服務點,則比m小的所有直徑長都不可能覆蓋所有服務點,因此可以利用這個特性來實作二分搜尋。 對於一個m值,要如何判斷是否能覆蓋所有服務點,可以實作一個函式check(m)來完成。 在check(m)中,我們要做的事情是,計算出當所有基地台直徑為m時,需要幾個基地台才能覆蓋所有服務點,實作方式也很簡單,遍歷存放服務點位置的陣列pos(要預先排序好),從第一個開始先加上m稱作now,表示第一個基地台的覆蓋範圍,再來只要範圍在now之間的位置表示能被覆蓋,可以直接跳過,但假如遇到一個新位置大於now,則需要新的基地台,而新的now的值就會是新位置+m,一直這樣實作到pos被遍歷完,最後回傳所需基地台的數量是否大於K(題目規定的基地台數量)即可(True or False)。 (小於等於K表示假如直徑為m時,能夠在規定以內覆蓋所有點,反之則表示假如直徑為m時需要比規定更多的基地台數量才能夠覆蓋所有點。如此一來就可以依據check(m)的回傳值判斷二分搜尋的下一步。)
//C++ language
#include<iostream>
#include<vector> //vector
#include<algorithm> //sort()
using namespace std;
int N,K;
vector<int>pos;
bool check(int m){
int now=pos[0]+m, cnt=1;
for(int i: pos){
if(i<=now) continue;
cnt++;
now=i+m;
}
return (cnt<=K);
}
int main(){
cin>>N>>K;
pos.resize(N);
for(int &x: pos) cin>>x;
sort(pos.begin(),pos.end());
int L=0,R=int(1e9)+1;
while(R-L>1){
int m=(L+R)/2;
if(check(m)) R=m;
else L=m;
}
cout<<R<<"\n";
return 0;
}

## Python language
N,K=map(int,input().split())
pos=[int(x) for x in input().split()]
pos.sort()
def check(m):
now=pos[0]+m
cnt=1
for i in pos:
if i<=now: continue
cnt+=1
now=i+m
return cnt<=K
L=0; R=int(1e9)+1
while R-L>1:
m=(L+R)//2
if check(m): R=m
else: L=m
print(R)
