2017/3/4 基地台

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)

相關文章