Re: [問題] 一題greedy (codeforces #451 pD)
看板Prob_Solve (計算數學 Problem Solving)作者outofyou時間6年前 (2018/01/31 21:28)推噓0(0推 0噓 1→)留言1則, 1人參與討論串3/3 (看更多)
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1517405286.A.E90.html
→
01/31 21:33,
6年前
, 1F
01/31 21:33, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
