[問題]n位整數拿掉m數字得到最大數值

看板Prob_Solve作者 (PatrickStar)時間10年前 (2013/11/13 22:05), 編輯推噓10(10推 0噓 4→)
留言14則, 7人參與, 最新討論串1/5 (看更多)
Given an integer (not necessary a decimal number) with n digits, we want to remove m (<=n) digits from this number such that the resulting number is as large as possible. Design an O(n) time algorithm to solve it. 可以提示如何下手嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.251.105.172
推
11/13 22:10, , 1F
找出第m大的數字，拿掉比他小的
11/13 22:10, 1F
推
11/13 22:14, , 2F
錯了remove m digits應該是保留比第m個大的
11/13 22:14, 2F
→
11/13 22:15, , 3F
這樣有辦法O(n)嗎? 是否可有詳細的解釋QQ
11/13 22:15, 3F
→
11/13 22:22, , 4F
一樓的作法對 231, 拿掉一個位數會錯: 23 < 31
11/13 22:22, 4F
推
11/13 22:53, , 5F
RMQ
11/13 22:53, 5F
推
11/13 23:00, , 6F
預處理O(n)+m次O(1)查詢=O(n)
11/13 23:00, 6F
推
11/13 23:08, , 7F
謝謝S大提醒。C大可以說的清楚點嗎?
11/13 23:08, 7F
推
11/13 23:34, , 8F
C大的做法應該是每次找從前數m'個第一次出現的最大digit吧
11/13 23:34, 8F
→
11/13 23:35, , 9F
這樣的話可以不用RMQ 畢竟O(n)預處理RMQ太刺激了www
11/13 23:35, 9F
推
11/13 23:38, , 10F
有個想法~可以從左到右用非嚴格遞減stack,直到pop m個為止
11/13 23:38, 10F
推
11/14 00:13, , 11F
//tioj.redirectme.net:8080/JudgeOnline/showproblem?
11/14 00:13, 11F
→
11/14 00:13, , 12F
problem_id=1397 據說是...
11/14 00:13, 12F
推
11/14 15:54, , 13F
慘了原來出過這題=口= 感謝樓上QQ
11/14 15:54, 13F
推
11/15 11:51, , 14F
UVa的11491-Erasing and Winning 也是這題喔
11/15 11:51, 14F
‣ 更多 PATRICKSTARS 的文章
文章代碼(AID): #1IWuSPQQ (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 5 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 PATRICKSTARS 的文章
文章代碼(AID): #1IWuSPQQ (Prob_Solve)