| 背包 | ||||||
| ||||||
| Description | ||||||
|
DS最近刚学会了背包。比如，给一个序列，问是否存在一个子集满足元素和为 X ， DS 会用一种方法：
xiaodao 觉得 DS 非常聪明，不过她想难为一下DS。她给了DS一个序列，序列中有 N（N ≤107）个正整数，满足1≤A1,Ai≤Ai+1,Ai≤109然后她让DS求这个序列的 “最小不可构造数”，也就是最小的 Y 使得 Y 不能表示为序列的某个子集中所有元素的和。 | ||||||
| Input | ||||||
|
第一行是一个整数 T 代表数据组数，以下是 T 组数据。每组数据第一行一个整数 N 代表本组数据一共有 N 个整数。第二行 N 个整数Ai 满足1≤A1,Ai≤Ai+1,Ai≤109所有的 N 加起来的和小于107 | ||||||
| Output | ||||||
|
对于每组数据，输出一个整数 Y 代表本组数据的最小不可构造数。 | ||||||
| Sample Input | ||||||
3
3
1 2 4
2
2 100000
4
1 2 3 4
| ||||||
| Sample Output | ||||||
8
1
11
| ||||||
| Hint | ||||||
|
对于第一组样例
对于第三组样例
|
我们考虑如果 <= S 的数全部可以表示的话，遇到一个新的数字 X ，如果
S + 1 < X 那么 S + 1 这个数字就无法表示，否则 1 ~ S + X 就可以表示。那么我们的做法就是——
记录前缀和 S ，和当前的数
X 进行比较。如果 S + 1 < X 输出 S + 1 否则序列结束的时候输出 S + 1.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 |
#include <stdio.h>#include <string.h>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;} |
原文：http://www.cnblogs.com/cancangood/p/3641741.html
