CSES – Missing Coin Sum

題目連結

題意

給 n 個硬幣，第 i 個硬幣的面額用 p[i] 表示。你可以用這些硬幣的子集合湊起來 (每個硬幣只能用一次)，問最小湊不出來的數字是多少?

解題方法

先將硬幣排序，用一個迴圈從 0 跑到 n 並且邊記錄總和，如果 a[i] - sum > 1 的話答案就是 sum + 1

如果 a[i] – sum <= 1:
0 ~ (sum + a[i]) 都可以被湊出來
因為我們可以跑到這裡的話就代表 0 ~ sum 都已經可以被湊出來，那把湊出來的值加上 a[i] 就能湊出 0 ~ (sum + a[i])
Ex.

• 本來可以湊出 sum + 1 – a[i] 的方式加上 a[i] 就可以湊出 sum + 1
• 本來可以湊出 sum + 2 – a[i] 的方式加上 a[i] 就可以湊出 sum + 2

如果 a[i] – sum > 1:
sum + 1沒辦法被湊出來因為 a[i] 至少是 sum + 2,
而本來在之前就湊不出來 sum + 1了 (全部加起來也只能湊成 sum)
現在不管拿前面的任何組合配上 a[i] 都一定會超過 sum +１
於是第一個湊不出來的值就會是 sum + 1

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin >> n;
    vector <long long> a(n);
    for(int i = 0;i < n;i++) 
        cin >> a[i];
    sort(a.begin(), a.end());
    long long sum = 0;
    for(int i = 0;i < n;i++){
        if(a[i]-sum > 1) {
            break;
        }
        sum += a[i];
    }
    cout << sum+1 << '\n';
}