問題描述
為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路 服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 N 個服務點，這 N 個服務點位在一條筆直的大道上，它們的位置(座標)係以與該大道一端的距離 P[i]來 表示，其中 i=0~N-1。由於設備訂製與維護的因素，每個基地台的服務範圍必須都一 樣，當基地台架設後，與此基地台距離不超過 R (稱為基地台的半徑)的服務點都可以 使用無線網路服務，也就是說每一個基地台可以服務的範圍是 D=2R(稱為基地台的直 徑)。現在電信公司想要計算，如果要架設 K 個基地台，那麼基地台的最小直徑是多少才能使每個服務點都可以得到服務。
基地台架設的地點不一定要在服務點上，最佳的架設地點也不唯一，但本題只需要求 最小直徑即可。以下是一個 N=5 的例子，五個服務點的座標分別是 1、2、5、7、8。
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
▲ |
▲ |
|
|
▲ |
|
▲ |
▲ |
|
假設 K=1，最小的直徑是 7，基地台架設在座標 4.5 的位置，所有點與基地台的距離都在半徑 3.5 以內。假設 K=2，最小的直徑是 3，一個基地台服務座標 1 與 2 的點， 另一個基地台服務另外三點。在 K=3 時，直徑只要 1 就足夠了。
評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依 正確通過測資筆數給分。其中：
第 1 子題組 10 分，座標範圍不超過 100，1≤ K ≤ 2，K < N ≤ 10。 第 2 子題組 20 分，座標範圍不超過 1,000，1≤ K < N ≤ 100。
第 3 子題組 20 分，座標範圍不超過 1,000,000,000，1≤ K < N ≤ 500。
第 4 子題組 50 分，座標範圍不超過 1,000,000,000，1≤ K < N ≤ 50,000。
輸入有兩行。第一行是兩個正整數 N 與 K，以一個空白間格。第二行 N 個非負整數 P[0]，P[1]，….，P[N-1]表示 N 個服務點的位置，這些位置彼此之間以一個空白間格。 請注意，這 N 個位置並不保證相異也未經過排序。本題中，K<N且所有座標是整數， 因此，所求最小直徑必然是不小於 1 的整數。
輸出最小直徑，不要有任何多餘的字或空白並以換行結尾。
範例一：輸入 5 2 5 1 2 8 7 範例二：輸入 5 1 7 5 1 2 8
範例一：正確輸出 3 範例二：正確輸出 7
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||