※ 引述《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解也是一個最佳解