题目描述

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

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

返回使用这些硬币能制造的 第 k 小 金额。

样例

输入： coins = [3,6,9], k = 3

输出： 9

解释：给定的硬币可以制造以下金额：
3 元硬币产生 3 的倍数：3, 6, 9, 12, 15 等。
6 元硬币产生 6 的倍数：6, 12, 18, 24 等。
9 元硬币产生 9 的倍数：9, 18, 27, 36 等。
所有硬币合起来可以产生：3, 6, 9, 12, 15 等。

输入：coins = [5,2], k = 7

输出：12

解释：给定的硬币可以制造以下金额：
5 元硬币产生 5 的倍数：5, 10, 15, 20 等。
2 元硬币产生 2 的倍数：2, 4, 6, 8, 10, 12 等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15 等。

限制

• 1 <= coins.length <= 15
• 1 <= coins[i] <= 25
• 1 <= k <= 2 * 10^9
• coins 包含两两不同的整数。

算法

(二分答案，容斥原理) $O(2^n (n + \log mk))$

1. 假设给定一个金额 $target$，可以通过容斥原理计算出这个金额的排名。如果这个排名小于 $k$，则需要增大 $target$，反之则需要减少 $target$。
2. 先预处理出所有硬币的组合，并求出每种组合的最小公倍数。在计算一个金额对于一种组合的出现次数时，只需要用这个金额除以组合的最小公倍数。
3. 根据容斥原理，如果一个组合中有奇数种硬币，则贡献为正，否则贡献为负。
4. 通过二分查找和容斥原理判定确定最终的 $target$。

时间复杂度

• 预处理每种组合最小公倍数的时间复杂度为 $O(2^n (n + \log m))$。
• 二分的下界为 $1$，上界为 $mk$，其中 $m$ 为硬币最大可能的面值。
• 每次判定的时间复杂度为 $O(2^n)$。
• 故总时间复杂度为 $O(2^n (n + \log mk))$。

空间复杂度

• 需要 $O(2^n)$ 的额外空间存储所有组合的最小公倍数和包含的硬币种类个数。

C++ 代码

#define LL long long

class Solution {
private:
    LL calc(LL target, const vector<pair<LL, int>> &g) {
        LL tot = 0;
        for (const auto &p : g)
            tot += p.second * (target / p.first);

        return tot;
    }

public:
    LL findKthSmallest(vector<int>& coins, int k) {
        const int n = coins.size();

        vector<pair<LL, int>> g;
        for (int s = 1; s < (1 << n); s++) {
            LL t = 1;
            int cnt = 0;

            for (int i = 0; i < n; i++)
                if ((s >> i) & 1) {
                    t = t * coins[i] / __gcd(t, (LL)(coins[i]));
                    ++cnt;
                }

            g.emplace_back(t, (cnt & 1) ? 1 : -1);
        }

        LL l = 1, r = (LL)(25) * k;
        while (l < r) {
            LL mid = (l + r) >> 1;

            if (calc(mid, g) < k) l = mid + 1;
            else r = mid;
        }

        return l;
    }
};