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

# APCS實作題2017年3月第4題：基地台 > 第1版：2023年2月17日 > 第2版：2023年6月14日，加上 C++ 程式碼 > 作者：王一哲 > 題目來源：[106年3月4日實作題第4題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1060304APCSImplementation.pdf) > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c575) ## 題目 ### 問題描述為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 $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;"/> 假設 $K = 1$，最小的直徑是 7，基地台架設在座標 4.5 的位置，所有點與基地台的距離都在半徑 3.5 以內。假設 $K = 2$，最小的直徑是 3，一個基地台服務座標 1 與 2 的點，另一個基地台服務另外三點。在 $K = 3$ 時，直徑只要 1 就足夠了。 ### 輸入格式輸入有兩行。第一行是兩個正整數 $N$ 與 $K$，以一個空白間格。第二行 $N$ 個非負整數$P[0]$，$P[1]$，….，$P[N-1]$ 表示 $N$ 個服務點的位置，這些位置彼此之間以一個空白間格。請注意，這 $N$ 個位置並不保證相異也未經過排序。本題中，$K < N$ 且所有座標是整數，因此，所求最小直徑必然是不小於 1 的整數。 ### 輸出格式輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。 ### 範例一：輸入 ``` 5 2 5 1 2 8 7 ``` ### 範例一：正確輸出 ``` 3 ``` ### 範例二：輸入 ``` 5 1 7 5 1 2 8 ``` ### 範例二：正確輸出 ``` 7 ``` ### 評分說明輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(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$。 ## Python 程式碼以下的程式碼說明已經寫在註解當中。於 ZeroJudge 測試結果，第16筆測資花費時間最久為 0.6 s，第14筆測資使用記憶體最多為 9.3 MB，通過測試。 ```python= # 由標準輸入讀取服務點數量 N、基地台數量 K、服務點位置 P N, K = map(int, input().split()) P = list(map(int, input().split())) P.sort() # P 由小到大排序 # 自訂函式 test，測試輸入的直徑 dis 是否能在 K 的基地台數量下涵蓋所有服務點位置 def test(dis): count = 0 # 已使用基地台數量 i = 0 # 服務點位置索引值 while i < N: # 當服務點位置還沒讀完時繼續執行 pos = P[i] + dis # 這個服務點右側距離為 dis 的位置 pos count += 1 # 已使用基地台數量加 1 if count > K: return False # 若已使用基地台數量大於 K，無法涵蓋所有服務點，回傳 False if P[-1] <= pos and count <= K: return True # 可以涵蓋所有服務點，回傳 True i += 1 # 先將索引值加 1 while P[i] <= pos: i += 1 # 若 P[i] 已在基地台範圍內，i 再加 1，直到 P[i] 不在基地台範圍內 return False # 若服務點位置都讀完時回傳 False if K == 1: print(P[-1] - P[0]) # 只有 1 個基地台，基地台直徑為最右側、最左側服務點的距離 else: # 其它狀況 L = 1 # 基地台半徑最小值為 1 R = int((P[-1] - P[0]) / K) + 1 # 基地台半徑可能的最大值，一定可以涵蓋所有服務點 while L < R: # L 小於 R 時繼續執行 M = int((L+R)/2) # 計算中間值 M if test(M): R = M # 呼叫自訂函式 test，代入 M 測試，若 M 可以涵蓋所有服務點，將最大值 R 重設為 M else: L = M + 1 # 若 M 無法涵蓋所有服務點，將最小值 L 重設為 M + 1 print(R) ``` ## C++ 程式碼以下的程式碼說明已經寫在註解當中。於 ZeroJudge 測試結果，第17筆測資花費時間最久為 97 ms，第16筆測資使用記憶體最多為 480 kB，通過測試。 ```cpp= #include <iostream> #include <algorithm> using namespace std; bool test(int, int*); int N, K; int main(int argc, char* argv[]) { // 由標準輸入讀取服務點數量 N、基地台數量 K、服務點位置 P cin >> N >> K; int P[N]; for(int i=0; i<N; i++) cin >> P[i]; sort(P, P+N); // P 由小到大排序 //for(int i=0; i<N; i++) cout << P[i] << " "; // 除錯用，印出排序後的服務點位置 P //cout << endl; if (K == 1) { cout << P[N-1] - P[0] << endl; // 只有 1 個基地台，基地台直徑為最右側、最左側服務點的距離 } else { // 其它狀況 int L = 1; // 基地台半徑最小值為 1 int R = int((P[N-1] - P[0]) / K) + 1; // 基地台半徑可能的最大值，一定可以涵蓋所有服務點 while(L < R) { // L 小於 R 時繼續執行 int M = int((L+R)/2); // 計算中間值 M if (test(M, P)) R = M; // 呼叫自訂函式 test，代入 M 測試，若 M 可以涵蓋所有服務點，將最大值 R 重設為 M else L = M + 1; // 若 M 無法涵蓋所有服務點，將最小值 L 重設為 M + 1 } cout << R << endl; } return 0; } // 自訂函式 test，測試輸入的直徑 dis 是否能在 K 的基地台數量下涵蓋所有服務點位置 bool test(int dis, int* P) { int count = 0; // 已使用基地台數量 int i = 0; // 服務點位置索引值 while(i < N) { // 當服務點位置還沒讀完時繼續執行 int pos = P[i] + dis; // 這個服務點右側距離為 dis 的位置 pos count++; // 已使用基地台數量加 1 if (count > K) return false; // 若已使用基地台數量大於 K，無法涵蓋所有服務點，回傳 false if (P[N-1] <= pos && count <= K) return true; // 可以涵蓋所有服務點，回傳 True i++; // 先將索引值加 1 while(P[i] <= pos) i++; // 若 P[i] 已在基地台範圍內，i 再加 1，直到 P[i] 不在基地台範圍內 } return false; // 若服務點位置都讀完時回傳 False } ``` ## 參考資料黃建庭（2019）。**C++程式設計解題入門融入程式設計競賽與APCS實作題（第二版）**。臺北市：碁峰資訊。 6-20 --- ###### tags:`APCS`、`Python`