作者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