Missing Coin Sum 硬币可以组成的连续面额上限

题目描述

You have n coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?

输入

The first input line has an integer n(1 ≤ n ≤ 2*105): the number of coins.
The second line has n integers x1,x2,...,xn(1 ≤ xi ≤ 109): the value of each coin.

输出

Print one integer: the smallest coin sum.

样例输入 Copy

5

2 9 1 2 7

样例输出 Copy

6

s变量记录连续最大上限

将硬币升序排序，每个硬币与s+1比较。

如果硬币比s+1大，那么之前已经可以拼成的所有组合中都不可能与这个硬币构成值为s+1的组合。（硬币=s+1，可以继续连续；=s，可以与1组合，达到继续连续的效果，以此类推）

贪心

代码

#includeusing namespace std;typedef long long ll;ll n,a[200009],ans=0,s=0;int main(){cin>>n;for(int i=0;i>a[i];s=0;sort(a,a+n);for(int i=0;is+1){break;}else s+=a[i];}cout<<s+1;return 0;}