作者PATRICKSTARS (PatrickStar)
看板Prob_Solve
標題[問題]n位整數拿掉m數字得到最大數值
時間Wed Nov 13 22:05:10 2013
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
1F：推 guest2:找出第m大的數字，拿掉比他小的 11/13 22:10
2F：推 guest2:錯了remove m digits應該是保留比第m個大的 11/13 22:14
3F：→ PATRICKSTARS:這樣有辦法O(n)嗎? 是否可有詳細的解釋QQ 11/13 22:15
4F：→ scwg:一樓的作法對 231, 拿掉一個位數會錯: 23 < 31 11/13 22:22
5F：推 CaptainH:RMQ 11/13 22:53
6F：推 CaptainH:預處理O(n)+m次O(1)查詢=O(n) 11/13 23:00
7F：推 guest2:謝謝S大提醒。C大可以說的清楚點嗎? 11/13 23:08
8F：推 pigalan:C大的做法應該是每次找從前數m'個第一次出現的最大digit吧 11/13 23:34
9F：→ pigalan:這樣的話可以不用RMQ 畢竟O(n)預處理RMQ太刺激了www 11/13 23:35
10F：推 pigalan:有個想法~可以從左到右用非嚴格遞減stack,直到pop m個為止 11/13 23:38
11F：推 suhorng://tioj.redirectme.net:8080/JudgeOnline/showproblem? 11/14 00:13
12F：→ suhorng:problem_id=1397 據說是... 11/14 00:13
13F：推 pigalan:慘了原來出過這題=口= 感謝樓上QQ 11/14 15:54
14F：推 atoi:UVa的11491-Erasing and Winning 也是這題喔 11/15 11:51