題意#
題目給定 \( n \) 個皆為正整數的硬幣面值。
需要從中挑選任意數量的硬幣組合，找出「無法湊出的最小正整數總和」。
例如硬幣面值為 1, 2, 5，可湊出 1, 2, 3 (=1+2)，但無法湊出 4，因此答案為 4。
思路#
本題可藉由觀察數字組合的單調性，使用連續區間擴充的「貪婪法（Greedy）」求解。
令變數 ans 代表「當前目標要湊出的最小正整數」。
因湊齊數字必定從 1 開始，初始時將 ans 設為 1。
若能湊出 1 到 ans-1 之間的所有整數，則加入一枚面值為 i 的硬幣後，可將湊出的區間擴充。
首先將所有硬幣從小到大排序。接著依序檢驗每枚硬幣的面值 i：
若硬幣面值
i小於或等於 當前目標ans：
表示這枚硬幣可以銜接既有的數字區間。
原本可湊出1到ans-1，加入i後可湊出的最大值延伸至(ans-1) + i。
因此，新的目標ans直接更新為ans + i。若硬幣面值
i大於 當前目標ans：
表示目前既有的硬幣組合加上新硬幣後，無法跨越ans產生連續數值（出現斷層）。
此時無法湊出ans，這個湊不出來的ans即為最終解答。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
vector<int> v(n);
for (auto &i : v) cin >> i;
// 將所有硬幣面值從小到大排序
sort(all(v));
// ans 代表當前預期要湊出的最小目標數字，從 1 開始
// 若成立則代表目前已能完美湊出 1 到 ans-1
int ans = 1;
for (auto &i : v) {
// 超過當前目標數字時，表示出現斷層無法湊出
if (i > ans) break;
// 否則，銜接硬幣擴展可湊出的上限區間
ans += i;
}
// 輸出第一個湊不出來的數字
cout << ans << '\n';
}
