※ 引述《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]的最佳解，得证。