本文涉及知識(shí)點(diǎn)

狀態(tài)壓縮 容斥原理 組合數(shù)學(xué)
二分查找算法合集

LeetCode100267. 單面值組合的第 K 小金額

給你一個(gè)整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給你一個(gè)整數(shù) k 。
你有無限量的每種面額的硬幣。但是，你 不能 組合使用不同面額的硬幣。
返回使用這些硬幣能制造的 第 kth 小 金額。
示例 1：
輸入： coins = [3,6,9], k = 3
輸出： 9
解釋：給定的硬幣可以制造以下金額：
3元硬幣產(chǎn)生3的倍數(shù)：3, 6, 9, 12, 15等。
6元硬幣產(chǎn)生6的倍數(shù)：6, 12, 18, 24等。
9元硬幣產(chǎn)生9的倍數(shù)：9, 18, 27, 36等。
所有硬幣合起來可以產(chǎn)生：3, 6, 9, 12, 15等。
示例 2：
輸入：coins = [5,2], k = 7
輸出：12
解釋：給定的硬幣可以制造以下金額：
5元硬幣產(chǎn)生5的倍數(shù)：5, 10, 15, 20等。
2元硬幣產(chǎn)生2的倍數(shù)：2, 4, 6, 8, 10, 12等。
所有硬幣合起來可以產(chǎn)生：2, 4, 5, 6, 8, 10, 12, 14, 15等。
提示：
1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 10⁹
coins 包含兩兩不同的整數(shù)。

容斥原理：小于等于mid的金額數(shù)量

如果不考慮重復(fù) ${\sum }_{i:}^{n?1}mid/coins[i]$ 考慮重復(fù)則很復(fù)雜。
以mid 12為例子，f(x) 表示用面值x的金幣能過組成小于等于mid的金額數(shù)量：
a , coins = {2,3}
面值2的倍數(shù)：2,4,6,8,10,12 f(2)=6，其中重復(fù)2個(gè)。
面值3的倍數(shù)：3,6,9,12 f(3) = 4 ,重復(fù)2個(gè)。
總數(shù)量：f(2)+f(3)-f(6) = 6-4-2=8。6是最小公倍數(shù)LCM
b，coins = {2,3,5}
面值5的倍數(shù)：5,10 = 2 ,其中重復(fù)一個(gè)。
新增加的數(shù)：
f(5) - f(LCM(5,2))-f(LCM(3,5))
如果一個(gè)數(shù) 同時(shí)10和15的倍數(shù)，則減重復(fù)了，要加回來：
及：
f(5) - f(LCM(5,2))-f(LCM(3,5)) + f(LCM(2,3,5))

注意： C++有系統(tǒng)函數(shù) lcm

二分

令 cnt(mid) 是小于等于mid的金額數(shù)。如果cnt(mid) < k，則mid一定不是解。我們要求第個(gè)一 cnt(mid)>=k 。 故用左開右閉空間。

單調(diào)性證明

mid1 > mid2 ，如果cnt(mid1)>=k 成立，則cnt(mid2)>=k 成立， 因?yàn)?mid1,mid2]中的數(shù)，要么讓返回值+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;
};

測(cè)試用例

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);}}

用狀態(tài)壓縮優(yōu)化代碼量（通過前置狀態(tài)計(jì)算后置狀態(tài))

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] 記錄 偶數(shù)個(gè)數(shù)的最小公倍數(shù)，vMask[1]記錄奇數(shù)個(gè)數(shù)的最小公倍數(shù)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;}
};

用狀態(tài)壓縮優(yōu)化代碼量（計(jì)算后置狀態(tài))

class Solution {
public:long long findKthSmallest(vector<int>& coins, int k) {	const int iMaskCount = 1 << coins.size();		vector<long long> vMask[2];//vMask[0] 記錄 偶數(shù)個(gè)數(shù)的最小公倍數(shù)，vMask[1]記錄奇數(shù)個(gè)數(shù)的最小公倍數(shù)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;}
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請(qǐng)下載《喜缺全書算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對(duì)大家說的話
聞缺陷則喜是一個(gè)美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。
子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛

測(cè)試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實(shí)現(xiàn)。