题意
给出一个长度为\(n(n \le 10^5)\)序列，求其每个子序列之和所组成的集合的\(mex\)
思路
这么水的题都没想出来，感觉自己脑子瓦特了。
假设前\(i\)位可以组成区间\([0,x]\)内的所有数。那么加入第\(i+1\)位后，就会让\([0+a[i+1],x + a[i + 1]]\)这个区间中的所有数字都可以组成。只要判断这个区间和原区间并起来是不是连续的就行了。
代码
/*
* @Author: wxyww
* @Date: 2019-04-21 11:49:09
* @Last Modified time: 2019-04-21 14:14:56
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int a[N];
int main() {
int n = read();
for(int i = 1;i <= n;++i) a[i] = read();
sort(a + 1,a + n + 1);
ll now = 0;
for(int i = 1;i <= n;++i) {
if(now < a[i] - 1) {
printf("%d\n",now + 1);
return 0;
}
now += a[i];
}
cout<<now + 1;
return 0;
}