列表

详情

NC25225. Mex

描述

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).


输入描述

The first line contains a single integer n(1 ≤ n ≤ 105).
The second line contains n non-negative integers Si(0 ≤ Si < 231).

输出描述

Print mex(S) in a single line.

示例1

输入: 

3
1 2 5

输出: 

4

说明:

S'=(), ∑S'=0

S'=(1), ∑S'=1

S'=(2), ∑S'=2

S'=(1,2), ∑S'=3

S'=(5), ∑S'=5

There
is no way for ∑S'=4, hence 4 is the answer.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 1252K, 提交时间: 2019-04-21 10:38:16 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[200005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    ll p=0;
    for(int i=1;i<=n;i++)
    {
        if(p+1>=a[i]) p+=a[i];
        else break;
    }
    cout<<p+1;
}

C++11(clang++ 3.9) 解法, 执行用时: 61ms, 内存消耗: 1148K, 提交时间: 2020-02-26 13:26:20 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000100];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		if(ans+1>=a[i])
		ans+=a[i];
		else break;
	}
	cout<<ans+1;
	return  0;
}

Python3(3.5.2) 解法, 执行用时: 112ms, 内存消耗: 10640K, 提交时间: 2019-04-22 18:18:40 

def main():
    n=int(input())
    s=list(map(int,input().split(" ")))
    s.sort()
    num=0
    for i in range(n):
        if num+1>=s[i]:
            num+=s[i]
        else:break
    print(num+1)
       
main()

上一题

© 2025 nowcoder.com