Minieye杯第十五届华中科技大学程序设计邀请赛现场同步赛 J题MAX

链接：

https://ac.nowcoder.com/acm/contest/700/J

来源：牛客网

Recently MINIEYE’s engineer M is working on neural network model training and he has found that if the output of the network is S = (S1, S2, …, Sn), then we can use mex(S) to predict the total training time of the neural network. Define mex(S) as:

Here S’ ≤ S means S’ is a subsequence of S, ∑S’ represents the sum of all elements in S’. Please note that S’ can be empty, and in that case ∑S’ is 0.

M needs your help to calculate mex(S).

题意：

一个长度为n的序列，S中任意几个元素的和 组合的集合为Q，求不在Q集合的最小非负整数（空集的和为0）

思路：

用 $s u m$ 记录当前 $[0, s u m]$ 的都存在被取到了。现在考虑第 $i$ 个数，下标从(0~n-1)

$if: nu[i]>sum+1
$

则 $s u m + 1$ 就是解.

$e l s e ： $

$s u m + = n a [i]$ ,即0~sum都可以被取到.

可以用循环不等式或者数学归纳法证明。

初始条件： $i = 0, s u m = 0$ .的时候成立.
假设当 $i = k$ 的时候假设成立.
那么我们证明 $i = k + 1$ 的时候上述假设成立

如果 $n a [i] > s u m + 1$ 那么 $s u m + 1$ 必定是一个解，因为 $s u m + 1$ 不等于其中任何一个数，也无法从多个数相加得到。

否则$[0,sum+na[i]] $都能被取到，因为$ [na[i]+1,na[i]+sum] $都可以由$ na[i]$和前面若干个数组成的序列得到。
故上述假设成立

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
ll na[100100];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll n,sum;
    cin>>n;
    for(int i=0;i>na[i];
    sort(na,na+n);
    sum=0ll;
    for(int i=0;i<n;++i){
        if(na[i]>sum+1) break;
        sum+=na[i];
    }
    cout<<sum+1<<endl;
    return 0;
}