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

Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間10年前 (2014/11/01 02:19)推噓0(0推 0噓 0→)

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

※ 引述《ooooooo (感覺銜接最重要...)》之銘言： : 使用以下例子說明題目要求： : input(A, k) , : A 表示目標數字 : k 表示可以使用的 digit 數目 : 補充條件(謝謝 E板友提醒)： : 1 <= A <= 10^15, 1<=k<=10 : Ex1 : Input(8000, 1) : 代表只能使用一種數字，來組成最接近 8000 的數，Output 為 7777 : Ex2 Input(3355798521 , 10) : 10 表示 0～9 均能使用, 故output 為 3355798521 : Ex3 Input(262004, 2) : Output 為： 262222 : 目前是往dp 的方向在思考，不過卡住了，請教板友這題目該怎麼解，謝謝關鍵測資會因為此題目的解法不同而有變化。採用以下暴力解當A很大，k = 1時，會跑非常久。本解題技巧：拆解數字字串串接為新數字求解。解法： 1.將A轉成字串，從len - 1開始loop每個字元，suppose index = x; Ex: 3355798521 2.從x位置拆解字串為head和tail，位置x所屬字元屬於tail Ex: x 在 len - 3的位置 head = 3355798, tail = 521 3.let tail 為 mid，higher bound 為 mid + 1, mid + 2 ... 到該位數最大的9999... lower bound 為 mid, mid - 1, mid - 2 ....... 到 0 分別產生新數字 head 接 higher bound 和 head 接 lower bound 各找到一組解符合所有位數 <= k 時停止。 Ex: higher bound = 3355798522, 3355798523 ....... lower bound = 3355798521, 3355798520 ....... 4.將所有候選解丟入容器，跑一次取最小絕對值者得解。實作程式： http://ideone.com/W6yVee for Java 目前版上測資全數通過且很快。但暴力解碰到測資 input(123456789, 1) 就會很慘。目前還沒有特別想到有什麼解法對所有測資都很快，那麼，先這樣唄！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414779543.A.F61.html