有想到个方法大家讨论讨论> <
不知道有没有哪边没考虑清楚的!!
能使用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这个答案了