B - Alyona and Mex

 

题意：

给出n个元素，元素可交换或减小，求最终缺少的最小正整数的最大值（mex）。

 

仔细观察我们不难看出当n个元素为从1~n递增时mex取最大值，如n=5时，1,2,3,4,5，mex取最大值6。所以我们就将数列尽量接近连续递增数列。

如1 3 3 3 6可改为1 2 3 3 4则取最大值mex为5。

 

附AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX=101000;

int a[MAX];

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int ans=1;
        sort(a,a+n);//排序 
        for(int i=0;i<n;i++){
            if(a[i]>=ans)//注意等于 
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}