本文涉及知识点
LeetCode3116. 单面值组合的第 K 小金额
给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。
你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
示例 1：
输入： 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等。
示例 2：
输入：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 * 109
coins 包含两两不同的整数。
容斥原理：小于等于mid的金额数量
如果不考虑重复
∑
i
:
n
−
1
m
i
d
/
c
o
i
n
s
[
i
]
\sum_{i:}^{n-1}mid/coins[i]
∑i:n−1mid/coins[i] 考虑重复则很复杂。
以mid 12为例子，f(x) 表示用面值x的金币能过组成小于等于mid的金额数量：
a , coins = {2,3}
面值2的倍数：2,4,6,8,10,12 f(2)=6，其中重复2个。
面值3的倍数：3,6,9,12 f(3) = 4 ,重复2个。
总数量：f(2)+f(3)-f(6) = 6-4-2=8。6是最小公倍数LCM
b，coins = {2,3,5}
面值5的倍数：5,10 = 2 ,其中重复一个。
新增加的数：
f(5) - f(LCM(5,2))-f(LCM(3,5))
如果一个数 同时10和15的倍数，则减重复了，要加回来：
及：
f(5) - f(LCM(5,2))-f(LCM(3,5)) + f(LCM(2,3,5))
注意： C++有系统函数 lcm
二分
令 cnt(mid) 是小于等于mid的金额数。如果cnt(mid) < k，则mid一定不是解。我们要求第个一 cnt(mid)>=k 。 故用左开右闭空间。
单调性证明
mid1 > mid2 ，如果cnt(mid1)>=k 成立，则cnt(mid2)>=k 成立， 因为(mid1,mid2]中的数，要么让返回值+1，要么让返回值不变。同理： cnt(mid2)>=k 不成立，则cnt(mid1)>=k，也不成立。
代码
核心代码
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
m_coins = coins;
long long left = 0, right = 1'000'000'000'000LL;
while (right - left > 1) {
const auto mid = left + (right - left) / 2;
if (Count(mid) >= k) {
right = mid;
}
else
{
left = mid;
}
}
return right;
}
long long Count(long long mid) {
vector<vector<long long>> vMask;
long long llRet = 0;
for (const auto& n : m_coins) {
vector<vector<long long>> vMask2;
for (const auto& v : vMask) {
vector<long long> v2;
for (const auto& llMask : v) {
const long long tmp = lcm(llMask, n);
if (tmp <= mid) {
v2.emplace_back(tmp);
}
}
vMask2.emplace_back(v2);
}
vMask2.emplace_back();
vMask2.back().emplace_back(n);
for (int i = 1; i < vMask2.size(); i++) {
vMask2[i].insert(vMask2[i].end(), vMask[i - 1].begin(), vMask[i - 1].end());
}
vMask2.swap(vMask);
}
for (int i = 0; i < vMask.size(); i++) {
for (const auto& iMask : vMask[vMask.size() - 1 - i]) {
llRet += (1 & i) ? -mid / iMask : mid / iMask;
}
}
return llRet;
}
vector<int> m_coins;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
测试用例
int main()
{
vector<int> nums = { 3,6,9 };
int k;
{
Solution sln;
nums = { 2,3,5,7,11,13,17,19,23,25,20,18 }, k = 1000000000;
auto res = sln.findKthSmallest(nums, k);
Assert(9LL, res);
}
{
Solution sln;
nums = { 3,6,9 }, k = 3;
auto res = sln.findKthSmallest(nums, k);
Assert(9LL, res);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
用状态压缩优化代码量（通过前置状态计算后置状态)
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
const int iMaskCount = 1 << coins.size();
vector<int> v01(iMaskCount),vLCM(iMaskCount,-1);
vector<int> vMask[2];//vMask[0] 记录 偶数个数的最小公倍数，vMask[1]记录奇数个数的最小公倍数
v01[0] = 0;
vLCM[0] = 1;
for (int iMask = 0; iMask < iMaskCount; iMask++) {
for (int j = 0; j < coins.size(); j++) {
if (!((1 << j) & iMask)) {
const int iNewMask = (1 << j) | iMask;
if (-1 != vLCM[iNewMask]) { continue; }
v01[iNewMask] = v01[iMask] ^ 1;
vLCM[iNewMask] = lcm(vLCM[iMask], coins[j]);
vMask[v01[iNewMask]].emplace_back(vLCM[iNewMask]);
}
}
}
long long left = 0, right = 1'000'000'000'000LL;
while (right - left > 1) {
const auto mid = left + (right - left) / 2;
long long cnt = 0;
for (const auto& ll : vMask[0]) {
cnt -= mid / ll;
}
for (const auto& ll : vMask[1]) {
cnt += mid / ll;
}
if (cnt >= k) {
right = mid;
}
else
{
left = mid;
}
}
return right;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
用状态压缩优化代码量（计算后置状态)
class Solution {
public:
long long findKthSmallest(vector<int>& coins, int k) {
const int iMaskCount = 1 << coins.size();
vector<long long> vMask[2];//vMask[0] 记录 偶数个数的最小公倍数，vMask[1]记录奇数个数的最小公倍数
vector<long long> v01(iMaskCount), vLCM(iMaskCount, -1);
{
v01[0] = 0;
vLCM[0] = 1;
for (int i = 0; i < coins.size(); i++) {
vLCM[1 << i] = coins[i];
}
for (int iNewMask = 1; iNewMask < iMaskCount; iNewMask++) {
const int iMask = (iNewMask - 1) & iNewMask;
v01[iNewMask] = v01[iMask] ^ 1;
vLCM[iNewMask] = lcm(vLCM[iMask], vLCM[iNewMask - iMask]);
vMask[v01[iNewMask]].emplace_back(vLCM[iNewMask]);
}
}
long long left = 0, right = 1'000'000'000'000LL;
while (right - left > 1) {
const auto mid = left + (right - left) / 2;
long long cnt = 0;
for (const auto& ll : vMask[0]) {
cnt -= mid / ll;
}
for (const auto& ll : vMask[1]) {
cnt += mid / ll;
}
if (cnt >= k) {
right = mid;
}
else
{
left = mid;
}
}
return right;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：