※ 引述《flere (人间失格)》之铭言：
: 有想到个方法大家讨论讨论> <
: 不知道有没有哪边没考虑清楚的!!
: 能使用k个数字, 我们可以穷举是哪k个
: 对于每一个可能的组合去求出最接近的数字
后面应该没什么大问题。但对于穷举k个，我考虑有规则的情况。
let d(x) 为 A 的 digits 数。
于是原本题目的解的domain可以为 d(A) 必定 > k，不然就直接输出A。
后面叙述的最高位想法是可以拿来规则化取候选 digits
1.对于 k = 1，候选 digits 为 最高位，和 (最高位 -1)
如果(最高位 - 1) == 0，则为9，
此特殊case适用尚未转化过的，且后面剩下位数必须都填9。
何谓转化请见2.
2.对于 k = 2 含以上，从d(A)里面取出并转化。直到k = 0为止不转化
input(262004, 2) 取最高位 2 并且当为解的第一位 并转化 input(62004, 1)
取 6 或 5，可以计算已经用掉2个digits 转化 (XXXX, 0)
XXXX用候选digits: 2, 6, 5填满，262222, 252222, 266666, 265555
举几个例子
case 1:
input(210004, 2) => 取 2 => input(10004, 1)
仅取1 => input(XXXX, 0) =>填满 212222, 211111
case 2:
input(8000, 1) => 取8, 7 => (XXX, 0) => 填满 8888, 7777
case 3:
input(1000, 1) => 取1, 9 (special case) => (XXX, 0) =>填满 1111 和 999
cae 4:
input(88449, 2) => 取8 => (8449, 1) => 取8, 7
分两路
=>(449, 1) => 取4 => (49, 0) => 88488, 88448, 88444
=>(449, 0) => 87888, 87777
应该可以实作了。
: 对于一个N位数的数字而言
: 我们的答案可能为N位数或N-1位数
: 想不到答案要N+1位数的case..
: 以N-1位数的答案ans而言
: ans肯定比要求的数字A还小
: 故ans要尽可能大
: 则ans会只由一种数字组成
: 接下来讨论ans为N位数的情况
: 由于我们已经穷举哪k个数能使用
: 所以我们可以从最高位开始决定要放什么数字
: 假设数字A的最高位数为m
: 则有三种情况:
: 1. 我们最高位放的数字>m, 这表示剩下N-1个位置, 我们要用k个数字组的尽量小
: 2. 我们最高位放的数字<m, 这表示剩下N-1个位置, 我们要用k个数字组的尽量大
: 3. 最高位放的数字=m, 则问题转化成(A-m*10^N,k), N-1个位数的问题
: 对于(1,2)而言, 尝试的数字必定是比m大(小)的里面最小(大)的, 只需尝试一次
: 且不须递回下去, 因为k个数字组最大最小可以直接算出
: 对于(3)则最多只有一种可能,
: 因此复杂度为(10取k)*(N个位数)*(每个位数3种可能)
===================================编辑分隔线=====================
补上实作连结
http://ideone.com/nOsGRz
修正特殊case：
当尚未进行转化，并且最高位减1 == 0的时候
判断首两位数为10才补满N - 1位数的9
否则取1和9继续递回。
修正结束条件：
当转化后k == 0但目前所在的digit之前尚未用过才停止开始填满。
若所在digit仍有用过那么索引要往后推，并继续递回。
详情看code就知道了，这样一来大部分case应该都能跑很快了。