問題描述
為因應資訊化與數位化的發展趨勢，某市長想要在城市的一些服務點上提供無線網路服務，因此他委託電信公司架設無線基地台。某電信公司負責其中 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 就足夠了。
輸入有兩行。第一行是兩個正整數 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
不公開 測資點#0 (5%): 2.0s , <1K
不公開 測資點#1 (5%): 2.0s , <1K
不公開 測資點#2 (5%): 2.0s , <1K
不公開 測資點#3 (5%): 2.0s , <1K
不公開 測資點#4 (5%): 2.0s , <1K
不公開 測資點#5 (5%): 2.0s , <1K
不公開 測資點#6 (5%): 2.0s , <1M
不公開 測資點#7 (5%): 2.0s , <1M
不公開 測資點#8 (5%): 2.0s , <1M
不公開 測資點#9 (5%): 2.0s , <1M
不公開 測資點#10 (5%): 2.0s , <1M
不公開 測資點#11 (5%): 2.0s , <1M
不公開 測資點#12 (5%): 2.0s , <1M
不公開 測資點#13 (5%): 2.0s , <1M
不公開 測資點#14 (5%): 2.0s , <1M
不公開 測資點#15 (5%): 2.0s , <1M
不公開 測資點#16 (5%): 2.0s , <1M
不公開 測資點#17 (5%): 2.0s , <1M
不公開 測資點#18 (5%): 2.0s , <1M
不公開 測資點#19 (5%): 2.0s , <1M
評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(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。
非官方測資，若有誤請不吝告知
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 31891 |
|
c575 | 844 | 2022-08-26 01:45 | |
| 35345 |
|
c575 | 886 | 2023-05-27 18:59 | |
| 33660 |
|
c575 | 780 | 2023-01-19 12:54 | |
| 31889 |
|
c575 | 620 | 2022-08-25 23:45 | |
| 29826 |
|
c575 | 1409 | 2022-04-04 00:01 |