PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題]n位整數拿掉m數字得到最大數值

看板Prob_Solve (計算數學 Problem Solving)作者CaptainH (Cannon)時間11年前 (2013/11/15 13:04)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串3/5 (看更多)

※ 引述《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