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.
可以提示如何下手吗?
作者:
guest2 (wayne)
2012-01-13 22:10:00找出第m大的数字，拿掉比他小的错了remove m digits应该是保留比第m个大的
楼主: PATRICKSTARS (PatrickStar) 2012-01-13 22:15:00
这样有办法O(n)吗? 是否可有详细的解释QQ
作者:
scwg ( )
2012-01-13 22:22:00一楼的作法对 231, 拿掉一个位数会错: 23 < 31
作者:
CaptainH (Cannon)
2012-01-13 22:53:00RMQ预处理O(n)+m次O(1)查询=O(n)
作者:
guest2 (wayne)
2012-01-13 23:08:00谢谢S大提醒。C大可以说的清楚点吗?
作者: pigalan (Tomato) 2012-01-13 23:34:00
C大的做法应该是每次找从前数m'个第一次出现的最大digit吧这样的话可以不用RMQ 毕竟O(n)预处理RMQ太刺激了www有个想法~可以从左到右用非严格递减stack,直到pop m个为止
作者:
suhorng ( )
2012-01-14 00:13:00//tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1397 据说是...
作者: pigalan (Tomato) 2012-01-14 15:54:00
惨了原来出过这题=口= 感谢楼上QQ
作者: atoi (atoi) 2012-01-15 11:51:00
UVa的11491-Erasing and Winning 也是这题喔