题目描述
3 个元素的集合{5，1，2}的所有子集的和分别是0,1,2,3,5,6,7,8。发现最小的不能由该集合子集拼出的数字是4。
现在给你一个n个元素的集合，问你最小的不能由该集合子集拼出的数字是多少。
输入输出格式
输入格式：
第一行两个整数n。
第n 个正整数ai，表示集合内的元素。
输出格式：
一行一个整数答案。
输入输出样例
输入样例#1：
3 5 1 2
输出样例#1：
4
说明
对于30% 的数据，满足n <=5。
对于60% 的数据，满足n <= 1000。
对于100% 的数据，满足n <= 100000,1 <= ai <=10^9。
保证ai互不相同。
1 /* 2 1、将每个读入的数从小到大排序。 3 2、sum表示当前的能合成的连续的最大数 4 如果num[i]>sum+1,也就是合不出sum+1，则不连续了，输出sum+1 5 否则sum+=num[i]。 6 为什么这样做呢 7 因为若num[i]<=sum， 8 即1~num[i]可以被合成， 9 那么sum+1~sum+num[i]间的数一定可以被合成 10 下一个可能不能被合成的数就是sum+num[i]+1了 11 */ 12 13 #include<iostream> 14 #include<cstdio> 15 #include<cmath> 16 #include<cstring> 17 #include<algorithm> 18 #include<map> 19 #define N 100005 20 using namespace std; 21 22 int n,num[N]; 23 long long sum; 24 25 inline void read(int &num) 26 { 27 char c=getchar(); 28 for(;!isdigit(c);c=getchar()); 29 for(;isdigit(c);c=getchar()){num=num*10+c-'0';}; 30 } 31 32 void init() 33 { 34 scanf("%d",&n); 35 for(int i=1;i<=n;i++) scanf("%d",&num[i]); 36 sort(num+1,num+n+1); 37 for(int i=1;i<=n;i++) 38 { 39 if(num[i]>sum+1) break; 40 sum+=num[i]; 41 } 42 printf("%lld",sum+1); 43 } 44 45 int main() 46 { 47 //freopen("lost.in","r",stdin); 48 //freopen("lost.out","w",stdout); 49 init(); 50 fclose(stdin); 51 fclose(stdout); 52 return 0; 53 }