Re: [问题] 0~9 挑k个数字, 组出最接近 A 的数字

楼主: EdisonX (卡卡兽)   2014-10-31 23:06:13
※ 引述《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 的方向在思考,不过卡住了,请教板友这题目该怎么解,谢谢
我觉得这题关键测资应该是类似 (8000, 1) , (88499 , 2)
假设 input(88499, 2) , 令 input[4:0] = {9,9,4,8,8} , len = 5
虚码大概如下
dig = 2; // 只能使用 2 位数
use_dig = 0; // 已使用位数
pool[10] = {0}; // 已使用过的数字放进来
int output[10]; // 最后的结果
for(i = len-1 ; i >= 0 ; i
作者: yr (Sooner Born Sooner Bred)   2014-10-31 23:55:00
(1000,1) 的话 999 这种状况也要考虑喔如果没限制答案位数要跟输入一样的话
作者: LPH66 (-6.2598534e+18f)   2014-11-01 00:24:00
条件只有最接近所以 (1000,1) 的答案确实是 999应该还有一种关键测资 (2243,2)这个答案是 2242 或 2244 或皆可题目应该要说明一下
作者: ooooooo (感觉衔接最重要...)   2014-11-01 00:50:00
(2243,2) => 2242 or 2244 皆可
楼主: EdisonX (卡卡兽)   2014-11-01 02:19:00
对呐,(1000,1) 的话又死在 1111 了 Orz看来要对剩 1 个 1 可选的做 special case 才"有机会"对

Links booklink

Contact Us: admin [ a t ] ucptt.com