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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.30.46 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1517326422.A.26A.html ※ 编辑: ckc1ark (140.112.30.46), 01/30/2018 23:40:40