c575: APCS 2017-0304-4基地台
Tags :
Accepted rate : 167人/195人 ( 86% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-06-02 15:31

Content

問題描述
為因應資訊化與數位化的發展趨勢,某市長想要在城市的一些服務點上提供無線網路服務,因此他委託電信公司架設無線基地台。某電信公司負責其中 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 就足夠了。

原題pdf檔

Input

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

Output

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

Sample Input
範例一:輸入
5 2
5 1 2 8 7
範例二:輸入
5 1
7 5 1 2 8
Sample Output
範例一:正確輸出
3
範例二:正確輸出
7
測資資訊:
記憶體限制: 64 MB
不公開 測資點#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
Hint :

評分說明
輸入包含若干筆測試資料,每一筆測試資料的執行時間限制(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。

非官方測資,若有誤請不吝告知

Tags:
出處:
2017年3月APCS [管理者: ]


ID User Problem Subject Hit Post Date
14126
HuangNO1 (雷姆醬)
c575 547 2018-06-14 23:26