作者GYLin (Lynx)
看板Prob_Solve
标题[问题] 一题greedy (codeforces #451 pD)
时间Tue Jan 30 22:21:34 2018
问题连结:
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, 可是到底为什麽这样做会对阿 = =
就只是要拆的时候就拆, 而且这样好像不会考虑到必须拆掉前面几根旗子的状况?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.176.203.175
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1517322097.A.51A.html
※ 编辑: GYLin (180.176.203.175), 01/30/2018 22:23:21
※ 编辑: GYLin (180.176.203.175), 01/30/2018 22:24:18
1F：→ outofyou: 不会有需要拆掉前面旗子的状况啊，前面距离都确定>=m了 01/30 23:13
我只是想说这样从尾巴做回来不会不一样吗
※ 编辑: GYLin (180.176.203.175), 01/31/2018 00:41:22
2F：推 ckc1ark: 要拆的旗子数一样的状况下可能会有很多组解 01/31 01:06
3F：→ outofyou: 从前面做、从後面做回来、从两端一起做都可以保持最佳解 01/31 23:52