有想到個方法大家討論討論> <
不知道有沒有哪邊沒考慮清楚的!!
能使用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這個答案了