題目：http://poj.org/problem?id=3258
在一個數線上有起點0和終點L，以及N個中繼點
現在想移除至多M個點，讓「最短的點間距離」最大
並且起點和終點不能移除
程式碼：http://codepad.org/zO7S0l3v
一眼就知道是二分答案的問題
定義f(x)是想達到最短點距x時，需要移除f(x)顆石頭
我們只要二分答案每次判斷f(x)是否在規定的M以內
從石頭1開始逐一決定是否要移除，貪心
AC以後發現我的程式碼和一些網路上解法都有個盲點
那就是我們都把終點L也當成一個石頭加進陣列裡
嚐試的過程居然也一派輕鬆的把終點給移除掉了…
但是這居然不影響答案的正確性，為什麼呢？
又是貪心：由於移除的總點數有限
而如果移除L的方案被認為可行的話
一定還有比這更好或一樣的移除方法
(細節說來這題測資似乎排除掉了一樣的可能性)
換句話說移除起點或終點，至多影響一條間距
但是移除中繼點都能一次讓兩條間距合併加寬，故更優
沒有留言:
張貼留言