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.
可以提示如何下手嗎?

找出第m大的數字，拿掉比他小的錯了remove m digits應該是保留比第m個大的

這樣有辦法O(n)嗎? 是否可有詳細的解釋QQ

一樓的作法對 231, 拿掉一個位數會錯: 23 < 31

RMQ預處理O(n)+m次O(1)查詢=O(n)

謝謝S大提醒。C大可以說的清楚點嗎?

C大的做法應該是每次找從前數m'個第一次出現的最大digit吧這樣的話可以不用RMQ 畢竟O(n)預處理RMQ太刺激了www有個想法~可以從左到右用非嚴格遞減stack,直到pop m個為止

//tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1397 據說是...

慘了原來出過這題=口= 感謝樓上QQ

UVa的11491-Erasing and Winning 也是這題喔