c293: APCS 2017-0304-4基地台
標籤 : APCS
通過比率 : 75% (9 人 / 12 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-10-06 22:20

內容 :

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

輸入說明

輸入有兩行。第一行是兩個正整數 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
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.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。

測資非官方的,是我自己產生的,若有誤請不吝告知

標籤:
APCS
出處:
2017年3月APCS [編輯: p3a_owhj (阿普二信) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」