作者kather (Kather)
看板Prob_Solve
标题[问题] Re: [问题] 0～9 挑k个数字, 组出最接近
时间Sun Nov 2 10:12:41 2014
其实这个问题应该考虑三个数就好
A,k
1.最高位-1低於A的最大值
2跟3用规则来定
考虑A=124351234,k=3.
1.取99999999
(A的高位1-1为0 降一位取最大)
2跟3:
先补满能补满的
即124
接下来遇到3，不在k个数(1,2,4)里面
从1，2，4组
大於351234的极小值
小於351234的最大值
就是411111跟244444
得到:
124411111,
124244444,
99999999
再从这三个数中取差距A最小的
最多取到两个
得到124,411111为解
例子2
A1312，k2
1.取999
2.
补满131,从1，3取低於2的最大值跟高於2的最小值，即1跟3
得
1311
1313
999
上面两数跟A差距都是1
此例解为1311与1313
例子3
A1000,k1
1.取999
2.补满1
取大於000的极小值与小於000的极大值
只有111
得
1111
999
而999与A差距最小
此例解为999
例子4
A6000,k1
1.取5555
2.补满6
取大於000的最小值与小於000的最大值
即666
得
5555
6666
则5555为解
-----
Sent from JPTT on my Asus ASUS_T00J.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.116.1.136
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414894364.A.BE5.html
※ 编辑: kather (140.116.1.136), 11/02/2014 10:26:51
※ 编辑: kather (140.116.1.136), 11/02/2014 10:28:41
1F：→ flere: (7099,2)是不是会错呀? 感觉您会输出7077, 答案应为7111 11/02 11:49
2F：→ kather: 炸了 XD 没考虑到这个case 11/02 12:20
3F：→ kather: 看来还要修正 11/02 12:22
4F：→ scwg: 搭火车的时候写的有点像这个做法的 greedy 硬干 11/03 14:28