原題目連結
Lucky貓翻譯

題解

直接硬解會變成相當高複雜度的 DP，但我們換個角度想：

當我們今天決定的是每家離 WIFI 最遠距離，則我們可以貪心決定至少需要幾台。
當允許距離增加，需要的 WIFI 至少不會變多；當距離縮短，需要 WIFI 並不會減少。

利用這性質，我們可以對距離進行二分搜，每個距離看需要的 WIFI 數量足不足夠。

貪心的方法：給定距離 d，從最小的一家開始，找到下一家沒有 WIFI，那我們至少要放一台 WIFI 給他。
而他要不是最前面的一家，就是前面每一家都已經有 WIFI。
因此，所有可覆蓋他家的位置中，他家位置 + d 可以覆蓋的其他人數量最優，
到他家位置 + d*2 全都可以覆蓋。把覆蓋的拿掉，再找下一家沒有 WIFI 的。

Time: 0.030, Rank: 124/962

來自小希的提醒

• 無