※ 引述《Leon (Achilles)》之铭言： : ※ 引述《PATRICKSTARS (PatrickStar)》之铭言： : : 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. : : 可以提示如何下手吗? : 嗯, 我看了一下. : Range Minimum Query (RMQ) 似乎不太对啊. : 举个简单的例子好了(有人已经点出来了) : 2-3-4-5-1-1, remove 2 digits : RMQ 应该会得到 2-3-4-5, : 但这题的最佳解应该是 4-5-1-1. : (希望我没有误解你的意思) 说明一下, 这里的 RMQ 是指Maximum. 以 A=[2,3,4,5,1,1] 为例，六个数字去掉两个等於保留四个， 这四位数的最高位数字 一定是来自 A 的前 6-4+1=3 项， 就是在子阵列[2,3,4]里找出最大的那个数，也就是 4。 找到第一个数之後就问题就缩小了，变成"从 [5,1,1] 留下三个元素使其值最大"， 这是个 trivial case，直接依序输出剩下的元素。 也可以用相同方法继续做： 这三位数的最高位数字一定来自[5,1,1]的前3-3+1=1项，也就是[5]， 迭代到最後就是答案了。 写成虚拟码: start = 0; count = n - m; RMaxQ( A, s, e ) = the left-most index of max value in A[s ... e] while( count > 0 ){ if( n - start == count ) print A[start ... n-1] else { idx = RMaxQ( A, start, n - count ) print A[idx] start = idx + 1 count = count - 1 } 时间复杂度是 RMQ预处理O(n) + (n-m)次O(1)查询 = O(n) 我推文的时候误会题目的意思(去掉m个看成保留m个), 在此修正 : 我认为这题呢, 要用 increasing sequence 的观念去看. : 从简单的 case 出发: : 1-2-3-4, increasing sequence, so everytime we remove, : we start from begining. : 4-3-2-1, decreasing sequence, then we remove from back. : Thus, when we work on it, : we start from making the leading sequence as a decreasing sequence, : then remove the inflection point. 我反而不懂你这句的意思 QQ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 120.126.141.168