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