哈尔滨理工大学第四届ACM程序设计竞赛F: 背包

DS最近刚学会了背包。比如，给一个序列，问是否存在一个子集满足元素和为 X ， DS 会用一种方法：

xiaodao 觉得 DS 非常聪明，不过她想难为一下DS。 她给了DS一个序列，序列中有 N（N ≤10⁷）个正整数，满足1≤A1 ,Ai≤Ai+1 ,Ai≤10⁹
然后她让DS求这个序列的 “最小不可构造数”，也就是最小的 Y 使得 Y 不能表示为序列的某个子集中所有元素的和。

第一行是一个整数 T 代表数据组数，以下是 T 组数据。
每组数据第一行一个整数 N 代表本组数据一共有 N 个整数。
第二行 N 个整数 Ai 满足 1≤A1 ,Ai≤Ai+1 ,Ai≤10⁹
所有的 N 加起来的和小于 10⁷

对于每组数据，输出一个整数 Y 代表本组数据的最小不可构造数。

3
3
1 2 4
2
2 100000
4
1 2 3 4

8
1
11

对于第一组样例

对于第三组样例

一开始以为是DP，后来想了下，但是由于数目太大而不好DP，后来想了下，只要前面的和+1达不到后面的那个数的话，那么前面得到的sum+1就是答案了。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[10000005];
int main()
{
    int i,j,n,t;
    long long sum;
    scanf("%d",&t);
    while(t--)
    {
        sum = 0;
        scanf("%d",&n);
        for(i = 0;i<n;i++)
        scanf("%d",&a[i]);
        sum = 0;
        for(i = 0;i<n;i++)
        {
            if(sum+1<a[i])
            break;
            sum+=a[i];
        }
        printf("%lld\n",sum+1);
    }

    return 0;
}