※ 引述《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应该都能跑很快了。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.203.156 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414825535.A.FDA.html 我用递回去产生填满，因为位数少，速度还算快。 ※ 编辑: bleed1979 (220.135.203.156), 11/01/2014 19:32:38