問題連結:
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, 可是到底為什麼這樣做會對阿 = =
就只是要拆的時候就拆, 而且這樣好像不會考慮到必須拆掉前面幾根旗子的狀況?