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