※ 引述《GYLin (Lynx)》之銘言： : 問題連結: : http://codeforces.com/contest/898/problem/D : 大意如下: : 給定一個沒排序過, 互不相同的n個座標(範圍1~10^6), : 將旗子放在這些坐標上, : 再給定m, k兩個數字, : 範圍為: : n >= k >= 1, : m >= 1 : 在任意連續m個座標上(ex: 2~m+1) : 只能有<k個旗子 : 請問最少要拆掉多少根旗子 : 我看別人的寫法是這樣(pseudocode) : 1.先排序陣列 a[0] ~ a[n-1] : 2.創一個queue (q) : 3. : for(int i = 0; i < n; i++) //從第0~第n-1根旗子 : { : while(!q.empty() && a[i] - q.front() >= m) q.pop(); : //要是queue有東西且目前座標 - 前面 >= m, 就重複拿掉 : if(q.size() < k-1) q.push(a[i]); : //能塞進queue就塞 : else cnt++; : //拆掉這根 : } : cnt 就是答案 : 感覺像某種greedy, 可是到底為什麼這樣做會對阿 = = : 就只是要拆的時候就拆, 而且這樣好像不會考慮到必須拆掉前面幾根旗子的狀況? 試著證明看看 greedy的證明蠻多是像這樣證的 先假設存在某個最佳解 然後在轉換成這個greedy解的過程中不會更糟 代表greedy解和這個最佳解一樣好 假設這個greedy解是a0, a1, a2, .... a{n-1} 其中ak=1代表第k個旗子要留 ak=0代表要拆 如果存在某個最佳解S: a0', a1', a2', ... a{n-1}' 一樣ak'=1代表要留 ak'=0代表要拆 那從頭開始比較一下 如果某個ai != ai' 以下分兩個case ## Case 1: ai=0, ai'=1 代表greedy解要拆 S要留 這是不可能的 因為greedy解在考慮到第i個旗子的時候 能留的話一定不會拆 ## Case 2: ai=1, ai'=0 代表greedy解有留 不過最佳解S拆掉了 這時候我們可以把下一個會留下來的aj'=1 和ai'=0互換 (一定存在aj'=1可以證看看) 得到另一個解S'和S幾乎一樣 其中ai'=1, aj'=0 這個一定也是一個符合條件的解 把所有ak都跑一遍 就會發現S變成greedy解的過程中並沒有丟失最佳解 代表greedy解也是一個最佳解 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.46 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1517326422.A.26A.html ※ 編輯: ckc1ark (140.112.30.46), 01/30/2018 23:40:40