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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.130.198.136 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1517405286.A.E90.html