小蓝有很多数字卡片每张卡片上都是数字 00 到 99。小蓝准备用这些卡片来拼一些数他想从 11 开始拼出正整数每拼一个就保存起来卡片就不能用来拼其它数了。小蓝想知道自己能从 11 拼到多少。例如当小蓝有 3030 张卡片其中 00 到 99 各 33 张则小蓝可以拼出 11 到 1010但是拼 1111 时卡片 11 已经只有一张了不够拼出 1111。现在小蓝手里有 00 到 99 的卡片各 20
可以用贪心的思想,从高位到低位逐个确定每一位上的数字,直到无法确定为止。
假设当前已经确定了前 k k 位数字,要确定第 k+1 k+1 位数字,可以从 9 9 到 0 0 逐个尝试,找到第一个可以用剩余卡片拼出的数字就确定该位数字,并将使用的卡片数量减去对应位数字的数量。
具体来说,设当前已经确定了前 k k 位数字,还剩下 c i [ j ] c_{i}[j] 张数字 j j 的卡片,要确定第 k+1 k+1 位数字,枚举从 9 9 到 0 0 的数字 d d,如果 c i [ d ] c_{i}[d] 大于等于 1 1,则将该位数字确定为 d d,将使用卡片数量减去 1 1,即 c i [ d ] ← c i [ d ] − 1 c_{i}[d] \leftarrow c_{i}[d]-1 。如果枚举完所有数字都无法确定该位数字,则前 k k 位数字无法组成更大的数。
代码如下:
原文地址: https://www.cveoy.top/t/topic/bC96 著作权归作者所有。请勿转载和采集!