小易邀请你玩一个数字游戏，小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来，然后你需要从这一系列数字中选取一部分出来让它们的和等于小易所说的数字。 例如： 如果{2,1,2,7}是你有的一系列数，小易说的数字是11.你可以得到方案2+2+7 = 11.如果顽皮的小易想坑你，他说的数字是6，那么你没有办法拼凑出和为6 现在小易给你n个数，让你找出无法从n个数中选取部分求和的数字中的最小数。 输入描述: 输入第一行为数字个数n (n ≤ 20) 第二行为n个数xi (1 ≤ xi ≤ 100000) 输出描述: 输出最小不能由n个数选取求和组成的数 输入例子: 3 5 1 2 输出例子: 4 这是牛客网上一名同学的做法：
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(void) { int n; cin >> n; vector<int> nums; while (n--) { int temp; cin >> temp; nums.push_back(temp); } sort(nums.begin(), nums.end()); int sum = 0; for (unsigned int i = 0; i < nums.size(); ++i) { if (nums[i] - sum > 1) { break; } else { sum += nums[i]; } } cout << sum + 1 << endl; }我在这里记录下我的理解思路： 这个题目可以转化为判断一个数字序列是否是连续的，如果不是连续的，断点在哪儿？证明如下： 假设有一系列数字a1，a2，a3，… ，an能自由组合成连续的0~kn个数，那么a1, a2, a3, …, an, a(n+1)就能自由组合成连续的0 ~kn和a(n+1) ~kn + a(n + 1)，若要证明0 ~ kn + a(n+1)是连续的，只要证明kn和a(n+1)是连续的，要想使kn和a(n+1)是连续的，只需要a(n+1) - kn <= 1即可。而这里的kn是等于a1 + a2 + a3 +… + an的。如果没有数字，当然能够得到0～0个连续的数字，也就是说当没有数字，kn为零时，假设成立，那只需要满足a（n+1） - kn <= 1即可得到任意连续的组合，也就是程序中所说的当 a(n + 1) - kn > 1时，a（n+1）和kn之间是不连续的，而不连续的最小数字就是kn+1。 若有不对之处，敬请指正。
