问题连结:
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, 可是到底为什么这样做会对阿 = =
就只是要拆的时候就拆, 而且这样好像不会考虑到必须拆掉前面几根旗子的状况?