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)

相關文章

分享此文：