3116. 单面值组合的第 K 小金额

题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。

返回使用这些硬币能制造的 第 ${\text{k}}^{\text{th}}$ 小 金额。

思路

在学习完丑数系列之后再回顾这道题，其实是 1201. 丑数 III 的扩展，1201 这道题只有三个数字，而这道题有 len(coins)<=15 个数字。实际上我们并不需要改 1201 的太多代码，修改 check 函数即可，那该怎么修改呢？

假设 coins = [a, b]，那么情况为：

$$\text{ugly}(x)=\frac{x}{a}+\frac{x}{b}-\frac{x}{a\times b}$$

假设 coins = [a,b,c]，情况为：

$$\text{ugly}(x)=\frac{x}{a}+\frac{x}{b}+\frac{x}{c}-\frac{x}{a\times b}-\frac{x}{a\times c}-\frac{x}{b\times c}+\frac{x}{a\times b\times c}$$

可以看到，对于 n 个硬币一共会有 $2^n-1$ 种情况，我们可以想到用位运算来计算：

假设 n=3，那么可以分成以下几种情况：

• 001, 010, 100 对应 $\frac{x}{a}+\frac{x}{b}+\frac{x}{c}$；
• 011, 101, 110 对应 $-\frac{x}{a\times b}-\frac{x}{a\times c}-\frac{x}{b\times c}$；
• 111 对应 $\frac{x}{a\times b\times c}$。

这是很显而易见的。那么我们遍历 range(1, 1<<len(coins))，再去根据位数去 coins 中取数据即可实现 check 函数：

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def check(num):
            cnt = 0
            for i in range(1, 1<<len(coins)):
                lcm_cnt = 1
                for j, coin in enumerate(coins):
                    if i >> j & 1:
                        lcm_cnt = lcm(lcm_cnt, coin)
                c = num//lcm_cnt
                cnt += c if i.bit_count() % 2 else -c
            return cnt >= k

接下来开始二分搜索，左右范围怎么取呢？左边可以取 1，那最大的值该取多少呢？假设 coins 中的最小值为 min(coins)，那么最坏情况下 min(coins)*k 一定满足要求。

这样就可以写出最终代码：

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def check(num):
            cnt = 0
            for i in range(1, 1 << len(coins)):
                lcm_cnt = 1
                for j, coin in enumerate(coins):
                    if i >> j & 1:
                        lcm_cnt = lcm(lcm_cnt, coin)
                c = num//lcm_cnt
                cnt += c if i.bit_count() % 2 else -c
            return cnt >= k
 
        l, r = 1, min(coins)*k
        while l < r:
            mid = l+(r-l)//2
            if check(mid):
                r = mid
            else:
                l = mid+1
        return l

优化：在 check 函数中我们进行了太多重复的计算，这一段可以缓存以提高速度。

想得太多

错误的想法

最开始是想统计数字的最小公倍数，然后获取这里面的所有数字并排序，第 k 小金额就是先整除所有数字再去取模数的值：

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        lcm = math.lcm(*coins)
        cov = []
        for num in coins:
            for i in range(1, lcm//num+1):
                cov.append(num*i)
        cov = list(set(cov))
        cov.sort()
 
        tms = k // len(cov)
        mod = k % len(cov)
 
        if mod == 0:
            return lcm*tms
        else:
            return lcm*tms+cov[mod-1]

OOM 了，想必是

        for num in coins:
            for i in range(1, lcm//num+1):
                cov.append(num*i)

这一段造成的。

结果发现是自己已经忘了容斥原理了，这下尴尬了。