作者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/m.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