作者bleed1979 (十三)
站內Prob_Solve
標題Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字
時間Sat Nov 1 02:18:59 2014
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1414779543.A.F61.html