作者flere (人間失格)
站內Prob_Solve
標題Re: [問題] 0～9 挑k個數字, 組出最接近 A 的數字
時間Sat Nov 1 13:01:58 2014
有想到個方法大家討論討論> <
不知道有沒有哪邊沒考慮清楚的!!
能使用k個數字, 我們可以窮舉是哪k個
對於每一個可能的組合去求出最接近的數字
對於一個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種可能)
補上一個測資:(7099,2) 答案為7111
若取前k個不同的數字當候選的話, 就會無法得到7111這個答案了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.152.218.19
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1414818126.A.BAE.html
1F：推 bleed1979: 能使用k個數字是指1 ~ k個皆可以。 11/01 13:53
2F：→ flere: 對阿, 這樣窮舉的話, 答案不見得會剛好k個數字 11/01 13:54
3F：→ flere: 如果舉了5個數字, 答案2個就行那就會得到2個數字的答案 11/01 13:54
4F：→ flere: 只是候選裡面有k個能讓我挑:D 11/01 13:55
※ 編輯: flere (58.152.218.19), 11/02/2014 11:55:20