# APCS實作題2017年3月第4題：基地台

> 第1版：2023年2月17日
> 第2版：2023年6月14日，加上 C++ 程式碼
> 第3版：2024年12月2日，讀了吳邦一教授的 AP325 講義之後重寫程式碼
> 作者：王一哲
> 題目來源：[106年3月4日實作題第4題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1060304APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c575)

<br />

## 題目

### 問題描述

為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 $N$ 個服務點，這 $N$ 個服務點位在一條筆直的大道上，它們的位置(座標)係以與該大道一端的距離 $P[i]$ 來表示，其中 $i = 0 \rightarrow N-1$。由於設備訂製與維護的因素，每個基地台的服務範圍必須都一樣，當基地台架設後，與此基地台距離不超過 $R$ (稱為基地台的半徑)的服務點都可以使用無線網路服務，也就是說每一個基地台可以服務的範圍是 $D = 2R$ (稱為基地台的直徑)。現在電信公司想要計算，如果要架設 $K$ 個基地台，那麼基地台的最小直徑是多少才能使每個服務點都可以得到服務。

基地台架設的地點不一定要在服務點上，最佳的架設地點也不唯一，但本題只需要求最小直徑即可。以下是一個 $N = 5$ 的例子，五個服務點的座標分別是 1、2、5、7、8。

<img height="80%" width="80%" src="https://i.imgur.com/ttu6ybw.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

假設 $K = 1$，最小的直徑是 7，基地台架設在座標 4.5 的位置，所有點與基地台的距離都在半徑 3.5 以內。假設 $K = 2$，最小的直徑是 3，一個基地台服務座標 1 與 2 的點，另一個基地台服務另外三點。在 $K = 3$ 時，直徑只要 1 就足夠了。
<br />

### 輸入格式

輸入有兩行。第一行是兩個正整數 $N$ 與 $K$，以一個空白間格。第二行 $N$ 個非負整數$P[0]$，$P[1]$，….，$P[N-1]$ 表示 $N$ 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 $N$ 個位置並不保證相異也未經過排序。本題中，$K < N$ 且所有座標是整數，因此，所求最小直徑必然是不小於 1 的整數。
<br />

### 輸出格式

輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。
<br />

### 範例一：輸入

5 2
5 1 2 8 7

### 範例一：正確輸出

3

<br />

### 範例二：輸入

5 1
7 5 1 2 8

### 範例二：正確輸出

7

<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 10 分，座標範圍不超過 100，$1 \leq K \leq 2$，$K < N \leq 10$。
- 第 2 子題組 20 分，座標範圍不超過 1,000，$1 \leq K < N \leq 100$。
- 第 3 子題組 20 分，座標範圍不超過 1,000,000,000，$1 \leq K < N \leq 500$。
- 第 4 子題組 50 分，座標範圍不超過 1,000,000,000，$1 \leq K < N \leq 50,000$。

<br />

## Python 程式碼

### 寫法1，二分搜尋法

花費時間最久為 0.3 s，使用記憶體最多為 9.8 MB，通過測試。

def test(d):  # 以直徑 d 測試是否能覆蓋所有的服務點
    used = 1  # 已用基地台數量，至少要有一個
    left = ps[0]  # 目前覆蓋範圍左端點，預設為服務點最左側
    right = left+d  # 目前覆蓋範圍右端點，為 left 加上 d
    for p in ps[1:]:  # 依序讀取 ps[1] ~ ps[-1]
        if p > right:  # 如果 p 在右端點的右側，出界
            used += 1  # 再用一個基地台
            left = p  # 以 p 當作新的左端點
            right = left+d  # 更新右端點
            if used > K: return False  # 使用的基地台數量大於 K，回傳 False
    return True  # 如果可以在 K 個基地台內覆蓋所有的服務點，回傳 True

N, K = map(int, input().split())  # 服務點數量 N，基地台數量 K
ps = sorted(list(map(int, input().split())))  # 服務點位置，由小到大排序
high = ps[-1] - ps[0]  # 最大的直徑，兩側服務點的距離
low = 2  # 最小的直徑，至少要是 2
while low <= high:  # 二分搜尋法
    mid = (high - low)//2 + low  # 中間值
    if test(mid): high = mid - 1  # 用 mid 當作直徑如果可以覆蓋所有服務點，將直徑調小
    else: low = mid + 1  # 否則將直徑調大
print(low)

<br /><br />

### 寫法2，跳躍二分搜尋法

花費時間最久為 0.4 s，使用記憶體最多為 9.8 MB，通過測試。

def test(d):  # 以直徑 d 測試是否能覆蓋所有的服務點
    used = 1  # 已用基地台數量，至少要有一個
    left = ps[0]  # 目前覆蓋範圍左端點，預設為服務點最左側
    right = left+d  # 目前覆蓋範圍右端點，為 left 加上 d
    for p in ps[1:]:  # 依序讀取 ps[1] ~ ps[-1]
        if p > right:  # 如果 p 在右端點的右側，出界
            used += 1  # 再用一個基地台
            left = p  # 以 p 當作新的左端點
            right = left+d  # 更新右端點
            if used > K: return False  # 使用的基地台數量大於 K，回傳 False
    return True  # 如果可以在 K 個基地台內覆蓋所有的服務點，回傳 True

N, K = map(int, input().split())  # 服務點數量 N，基地台數量 K
ps = sorted(list(map(int, input().split())))  # 服務點位置，由小到大排序
d = 0  # 直徑起始值
jump = (ps[-1] - ps[0])//2  # 跳躍距離，初始值為兩側基地台距離的一半
while jump:  # 跳躍二分搜尋法，當 jump 不為 0 時繼續執行
    if not test(d+jump): d += jump  # 用 d+jump 當作直徑如果無法覆蓋所有服務點，將直徑調大
    else: jump >>= 1  # 否則將 jump 除以 2 再繼續測試
# 結束 while 迴圈時 d 為無法覆蓋所有服務點的基地台直徑最大值
print(d+1)  # 答案為 d+1

## C++ 程式碼

### 寫法1，二分搜尋法

花費時間最久為 14 ms，使用記憶體最多為 540 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;  // 服務點數量 N，基地台數量 K
vector<int> ps (50000);  // 服務點位置，長度先設定為題目的最大值

bool test(int d) {  // 以直徑 d 測試是否能覆蓋所有的服務點
    int used = 1;  // 已用基地台數量，至少要有一個
    int left = ps[0];  // 目前覆蓋範圍左端點，預設為服務點最左側
    int right = left+d;  // 目前覆蓋範圍右端點，為 left 加上 d
    for(int i=1; i<N; i++) {  // 依序讀取 ps[1] ~ ps[-1]
        if (ps[i] > right) {  // 如果 ps[i] 在右端點的右側，出界
            used++;  // 再用一個基地台
            left = ps[i];  // 以 ps[i] 當作新的左端點
            right = left+d;  // 更新右端點
            if (used > K) return false;  // 使用的基地台數量大於 K，回傳 false
        }
    }
    return true;  // 如果可以在 K 個基地台內覆蓋所有的服務點，回傳 true
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;  // 服務點數量 N，基地台數量 K
    ps.resize(N);  // 調整 ps 的長度為 N
    for(int i=0; i<N; i++) cin >> ps[i];  // 讀取 N 個位置
    sort(ps.begin(), ps.end());  // 由小到大排序
    int high = ps.back() - ps[0];  // 最大的直徑，兩側服務點的距離
    int low = 2;  // 最小的直徑，至少要是 2
    while(low <= high) {  // 二分搜尋法
        int mid = (high - low)/2 + low;  // 中間值
        if (test(mid)) high = mid - 1;  // 用 mid 當作直徑如果可以覆蓋所有服務點，將直徑調小
        else low = mid + 1;  // 否則將直徑調大
    }
    cout << low << "\n";
    return 0;
}

<br /><br />

### 寫法2，跳躍二分搜尋法

花費時間最久為 15 ms，使用記憶體最多為 540 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;  // 服務點數量 N，基地台數量 K
vector<int> ps (50000);  // 服務點位置，長度先設定為題目的最大值

bool test(int d) {  // 以直徑 d 測試是否能覆蓋所有的服務點
    int used = 1;  // 已用基地台數量，至少要有一個
    int left = ps[0];  // 目前覆蓋範圍左端點，預設為服務點最左側
    int right = left+d;  // 目前覆蓋範圍右端點，為 left 加上 d
    for(int i=1; i<N; i++) {  // 依序讀取 ps[1] ~ ps[-1]
        if (ps[i] > right) {  // 如果 ps[i] 在右端點的右側，出界
            used++;  // 再用一個基地台
            left = ps[i];  // 以 ps[i] 當作新的左端點
            right = left+d;  // 更新右端點
            if (used > K) return false;  // 使用的基地台數量大於 K，回傳 false
        }
    }
    return true;  // 如果可以在 K 個基地台內覆蓋所有的服務點，回傳 true
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;  // 服務點數量 N，基地台數量 K
    ps.resize(N);  // 調整 ps 的長度為 N
    for(int i=0; i<N; i++) cin >> ps[i];  // 讀取 N 個位置
    sort(ps.begin(), ps.end());  // 由小到大排序
    int d = 0;  // 直徑初始值為 0
    int jump = (ps.back() - ps[0])/2;  // 跳躍距離，預設為兩側服務點距離的一半
    while(jump) {  // 跳躍二分搜尋法
        if (!test(d+jump)) d += jump;  // 用 d+jump 當作直徑如果無法覆蓋所有服務點，將直徑調大
        else jump >>= 1;  // 反之為跳太遠，將 jump 除以 2
    }
    cout << d+1 << "\n";  // 結束 while 迴圈時 d 為無法覆蓋所有服務點的基地台直徑最大值，答案為 d+1
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`