問題描述
為因應資訊化與數位化的發展趨勢,某市長想要在城市的一些服務點上提供無線網路服務,因此他委託電信公司架設無線基地台。某電信公司負責其中 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
評分說明
輸入包含若干筆測試資料,每一筆測試資料的執行時間限制(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 | seer852741@g ... (St418) | c575 | 1003 | 2022-08-26 01:45 | |
35345 | luray0601@gm ... (QWERTYPIG) | c575 | 1146 | 2023-05-27 18:59 | |
33660 | a110608@ctes ... (鍾均) | c575 | 932 | 2023-01-19 12:54 | |
31889 | seer852741@g ... (St418) | c575 | 732 | 2022-08-25 23:45 | |
29826 | dfd8282@gmai ... (fishhh) | c575 | 1559 | 2022-04-04 00:01 |