描述

一條街道安裝無線網絡，需要放置M個路由器。整條街道上一共有N戶居民，分布在一條直線上，每一戶居民必須被至少一臺路由器覆蓋到。現在的問題是所有路由器的覆蓋半徑是一樣的，我們希望用覆蓋半徑盡可能小的路由器來完成任務，因為這樣可以節省成本。(1 ≤ N, M ≤ 100000)

---

分析

首先這種問題可以采用二分答案的方法. 嘗試當前路由器覆蓋范圍能否覆蓋所有居民點. 那么這里如果采用二分半徑的方法, 會出現實數, 所以采用 wxjlzbcd 的方法, 采用二分直徑, 最后實數折半輸出.

在嘗試答案可行性的時候, 為了快速查找從當前居民點可以覆蓋到的最遠居民點, 再采用一次二分查找 (upper_bound) 找到剛好覆蓋不到的一個點, 也就是下一個起點. 注意這里的幾個變量的初值和邊界值需要好好考慮一下.

---

代碼

https://code.csdn.net/snippets/607845

總結

以上是生活随笔為你收集整理的路由器安置(Routing)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。