※ 引述《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, 可是到底為什麼這樣做會對阿 = = : 就只是要拆的時候就拆, 而且這樣好像不會考慮到必須拆掉前面幾根旗子的狀況? 令最佳解中座標最小的旗座標為a[i_1]!=a[0]， 則最佳解=a[i]+可容下旗座標a[i_1]的最佳解(a[i_1]+m以後)。 但是因為a[0]<a[i_1]，所以必存在最佳解a[0]+可容下旗座標a[i_1]的最佳解(a[i_1]+m 以後)。 用數學歸納法： 取某座標x小於等於a[i_n](最佳解第n小的旗座標a[i_n])，必保留取第n+1小的旗座標 a[i_n+1]的最佳解，得證。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.130.198.136 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1517405286.A.E90.html