作者EdisonX (卡卡兽)
站内Prob_Solve
标题Re: [问题] 0～9 挑k个数字, 组出最接近 A 的数字
时间Fri Oct 31 23:06:13 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 的方向在思考，不过卡住了，请教板友这题目该怎麽解，谢谢
我觉得这题关键测资应该是类似 (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--)
{
// 如果 input[i] 已在 pool 里使用过的话，直接填入插入
if(TRUE == lookup_exist( input[i] , pool[0:dig] ) )
{
output[i] = input[i];
}
else // input[i] 没在 pool 里使用过
{
if( dig - use_dig == 1) break; // 剩最後一位可挑时跳出去
else { output[i] = input[i] ; dig++; } //非最後一位，直接填入
}
}
if(i < 0)
{
print( output ) ; // 全挑完, 直接输出答案
exit
}
else
{
// 这里还有一位可挑 ,
// 依序挑出 input[i-1], input[i] , input[i+1] 做最後排列，
// 看哪个结果比较好
(A)
}
---------------------
参考下。
目前我想到的算法如上，没完整 implement 出来,
另外 (A) 部份也没再细思，但推了下整个流程应是可行的？
--
「自从我学了 C# , 人都变聪明 , 考试都考一百分」
「自从我学了 VB , 皮肤都变好 , 人也变漂亮了 」
「自从我学了 Java , 明显变壮 , 个子也变高了 」
「自从我学了 C++ , 内分泌失调 , 头都秃了... 」
< Kuso 星爷语录 >
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.177.74.8
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414767978.A.32B.html
※ 编辑: EdisonX (180.177.74.8), 10/31/2014 23:07:53
1F：→ yr: (1000,1) 的话 999 这种状况也要考虑喔 10/31 23:55
2F：→ yr: 如果没限制答案位数要跟输入一样的话 10/31 23:56
3F：推 LPH66: 条件只有最接近所以 (1000,1) 的答案确实是 999 11/01 00:24
4F：→ LPH66: 应该还有一种关键测资 (2243,2) 11/01 00:26
5F：→ LPH66: 这个答案是 2242 或 2244 或皆可题目应该要说明一下 11/01 00:26
6F：推 ooooooo: (2243,2) => 2242 or 2244 皆可 11/01 00:50
7F：→ EdisonX: 对呐,(1000,1) 的话又死在 1111 了 Orz 11/01 02:19
8F：→ EdisonX: 看来要对剩 1 个 1 可选的做 special case 才"有机会"对 11/01 02:23