## 金錢問題
???+note "換零錢(互相整除)"
給一個長度為 $n$ 的遞增序列 $a_1, \ldots ,a_n$,代表每種硬幣的面額,每種硬幣的數量都有無限個,問最少選幾個硬幣恰能湊出 $k$ 元
$n\le 10^6,a_{i+1}$ % $a_i=0$
??? note "思路"
例如說 k = 1384,a 是新台幣,那我們就可以附 1 個 1000、3 個 100、1 個 50、3 個 10、4 個 1,但為什麼這樣一定是好的 ?
【引理 1】: 在面額互相整除的情況下,若存在面額 x 的貨幣,且面額在 x 之下的總和超過 x,則必定能夠透過換錢使得面額在 x 以下的貨幣總和不到 x 且使貨幣數量更少
證明: 見此處
【引理 2】: 在面額互相整除的情況下,盡量使用面額較大的貨幣,可讓使用的貨幣數量最少
證明: 由 【引理 1】 得知,若最佳解未使用盡量大面額的貨幣(也就是,存在一個面額 x,使得面額在 x 以下(不含 x)的貨幣總和超過 x),則必定可以透過換前,使其成為更好的一組解,與最佳解的前提矛盾
??? note "code"
```cpp linenums="1"
#include
#define int long long
#define ALL(x) x.begin(),x.end()
using namespace std;
const int MAXN = 1e6 + 5;
int n, k, a[MAXN];
signed main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
ans += k / a[i];
k %= a[i];
}
cout << ans << '\n';
}
```
???+note "換零錢(不互相整除)[CSES - Coin Combinations II](Coin Combinations II)"
給一個長度為 $n$ 的遞增序列 $a_1, \ldots ,a_n$,代表每種硬幣的面額,每種硬幣的數量都有無限個,問最少選幾個硬幣恰能湊出 $k$ 元
$n\le 100, 1\le k, a_i\le 10^6$
??? note "思路"
dp(i) = 是否能湊出 i,去執行類似背包問題就可以了,複雜度 O(nk)
???+note "[TIOJ 1579.來自未來的新台幣](https://tioj.ck.tp.edu.tw/problems/1579)"
給長度為 $n$,⾯額分別為 $1,5,10,50,100,500,1000,\ldots$ 的錢幣,第 $i$ 個錢幣的數量為 $c_i$,能湊出的金額共有多少種
$1\le n\le 19$
??? note "思路"
若小的足以表達大的,就將大的都換成小的。例如 1 元有 5 個,5 元有 2 個,那麼因為 1 * 5 > 5,所以可將 5 都換成 1 元,變成 1 元有 15 個,若 1 元只有 3 個,那麼湊不出來 4,也就不能換了,兩者變成獨立的。
所以我們就依序看大的能不能換成當前最小的即可,最後的答案為 $(c_1 + 1)\cdot (c_2 + 1) \ldots (c_k+1) - 1$
> 參考自 : [PTT](https://www.ptt.cc/bbs/tutor/M.1304705220.A.35E.html)
??? note "code"
```cpp linenums="1"
#include
#define int long long
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
using namespace std;
using pii = pair;
const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;
int a[maxn], cnt[maxn];
signed main() {
int n;
cin >> n;
a[0] = 1;
for (int i = 1; i < n; i++) {
if (i & 1) {
a[i] = a[i - 1] * 5;
} else {
a[i] = a[i - 1] * 2;
}
}
int cur = 0;
for (int i = 0; i < n; i++) {
cin >> cnt[i];
if (i == 0) {
continue;
}
if (a[cur] * cnt[cur] >= a[i]) {
cnt[cur] += (a[i] / a[cur]) * cnt[i];
cnt[i] = 0;
} else {
cur = i;
}
}
int ans = 1;
for (int i = 0; i < n; i++) {
if (cnt[i]) {
ans = (ans * ((cnt[i] + 1) % M)) % M;
}
}
cout << (ans - 1 + M) % M << '\n';
}
```
???+note "[CSES - Missing Coin Sum](https://cses.fi/problemset/task/2183)"
給 $n$ 個錢幣,面額是 $a_1, \ldots ,a_n$,問最小湊不出來的面額是多少
$n\le 2\times 10^5, 1\le a_i \le 10^9$
??? note "思路"
若小的足換大,則大**必定**要換小,跟上一題一樣,重複直到小不足以換大為止
這邊要注意,跟上一題不同的是,若小的金額跟大的只差一,也是可以將大換小的,例如說 1 元有 4 個,5 元有 1 個,這樣其實 [0, 9] 都湊得出來,所以也是可以把這個 5 元換成 5 個 1 元
??? note "code"
```cpp linenums="1"
#include
#define int long long
using namespace std;
const int INF = 9e18;
const int MAXN = 2e5 + 5;
int n, m;
int a[MAXN];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int mx = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > mx + 1) {
cout << mx + 1 << "\n";
exit(0);
}
mx = max(mx, mx + a[i]);
}
cout << mx + 1 << "\n";
}
```
???+note "[CSES - Missing Coin Sum Queries](https://cses.fi/problemset/task/2184)"
給 $n$ 個錢幣,面額是 $a_1, \ldots ,a_n$,有 $q$ 筆詢問:
- $\text{query}(l,r):$ 問只能使用 $a_l, \ldots ,a_r$,最小湊不出來的面額是多少
$n,q\le 2\times 10^5, 1\le a_i \le 10^9$
??? note "思路"
假如說我目前能湊出 [1, x] 的這些數字,代表我們足以表達面額為 x + 1 的硬幣,可將 x + 1 的硬幣金額都加過來,假如說是 c,則能湊出的數字範圍就變成了 [1, c],若此時 x = c,代表已經產生一個 gap 了,沒辦法再換,答案即為 x + 1。舉例來說我現在能湊出 [1, 4],可表達 4 + 1 = 5 元,但 5 元沒有,所以最小湊出來的就是 5 元。
更具體一點的例子,假如說 a = [1, 1, 3, 3, 5, 8, 25, 30, 40],當前 <= 1 的硬幣加起來是 2,所以我足以表達 2 + 1 = 3,而 <= 3 的硬幣加起來是 8,代表我們足以表達 8 + 1 = 9,而 <= 9 的硬幣加起來是 21,代表我們足以表達 21 + 1 = 22,而 <= 22 的硬幣加起來是 21,沒辦法再換了
所以我們需要一個資料結構來快速 query(L, R, v): 詢問在 L, R 數字介於 1, v 的總和,這可以將 point(i, a[i]) 打在二維平面上,問題就變成詢問一個矩形區域。這可以用持久化線段樹紀錄 n 個版本,在 seg[R] - seg[L - 1] 上詢問就好了
因為換錢每次的金額幾乎是倍增的(不是每一項都倍增,是隔兩項倍增),所以複雜度為 O(n * log C * log n)
???+note "[CF 1303 D. Fill The Bag](https://codeforces.com/contest/1303/problem/D)"
給一個長度為 $m$ 的序列 $a_1, \ldots ,a_m$,$a_i$ 都是 2 的冪次。每次操作可將一個 $a_i$ 拆兩半,問最少幾次操作才能挑一些 $a$ 裡面的元素來組成 $n$
$m\le 10^5, 1\le n\le 10^{18}, 1\le a_i \le 10^9$
??? note "思路"
以二進制的角度來考慮此題,將 $m$ 以二進制表示,我們的目標就是要讓 $m$ 的二進制裡的每一個 1 都有被貢獻,有兩個觀察:
- 可將高位分解成低位(在 $a_i$)
- 高位能由低位組成
從大到小考慮的話,若高位不夠借,那我就必須從低位借,這樣又要處理左邊又要處理右邊很麻煩。不如我們從小到大考慮,若低位不夠用則需要跟最近的高位借,將高位分解成低位使用,在過程中將低位換成高位,這樣實作起來就很順了
也可以將低位目前的金額總和記錄起來,令他為 sum,若發現 sum 大於當前位元 2^i,則可將 sum -= 2^i。若覺得有點困惑,這是應用到換錢問題的引理,可見此處查看證明。
??? note "code"
```cpp linenums="1"
#include
#include