c575: APCS 2017-0304-4基地台

c575: APCS 2017-0304-4基地台

題 意:

在 一 條 數 線 上 有 $K$ 個 基 地 台 及 $N$ 個 服 務 點。

每 個 基 地 台 都 有 相 同 的 服 務 範 圍 $D$ (基 地 台 的 服 務 半 徑 * 2)，

而 每 個 服 務 點 都 必 須 在 每 個 基 地 台 的 服 務 範 圍 裡 才 能 得 到 服 務。

給 你 $N$ 個 服 務 點 的 位 置，以 每 個 服 務 點 都 能 接 收 服 務 為 前 提，求 $K$ 個 基 地 台 的 最 小 直 徑。

solve:

對 $N$ 個 點 排 序，並 計 算 點 的 距 離，找 前 $K - 1$ 大 的 做 分 割 點，再 分 成 $K$ 群。

確 實，理 論 上 可 行。但 是 明 顯 的 難 以 實 作，並 且 時 間 複 雜 度 高。

因 為 答 案 只 可 能 在 (最 遠 的服 務 點 - 最 近 的 服 務 點) 與 (1) 之 間，因 此 可 以 用 二 分 搜 解 答。

理 論 複 雜 度 $O(log$ $maxDis)$，因 為 要 驗 證 的 關 係，實 際 還 會 在 高 一 點，但 解 決 此 題 足 矣。

code: