作者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/cn.aspx?n=bbs/Prob_Solve/M.1414779543.A.F61.html