[問題] 一題greedy (codeforces #451 pD)
看板Prob_Solve (計算數學 Problem Solving)作者GYLin (Lynx)時間6年前 (2018/01/30 22:21)推噓1(1推 0噓 2→)留言3則, 2人參與討論串1/3 (看更多)
問題連結:
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://www.ptt.cc/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
→
01/30 23:13,
6年前
, 1F
01/30 23:13, 1F
我只是想說這樣從尾巴做回來不會不一樣嗎
※ 編輯: GYLin (180.176.203.175), 01/31/2018 00:41:22
推
01/31 01:06,
6年前
, 2F
01/31 01:06, 2F
→
01/31 23:52,
6年前
, 3F
01/31 23:52, 3F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
