2、小明和完美序列.docx

解题思路

本题主要考察选手stl的简单运用。

由完美序列的定义可以知道，序列中每个数字的个数，要么是等于它本身，要么就是一个没有。那么很显然的，如果一个数字出现的次数比它本身大，我们就选择删掉多出的，这样肯定比完全删除是更优的，只有在当一个数字出现的次数小于它本身的时候，这种情况，我们不得不选择全部删除。所以解决这个问题，只要统计每个数字出现的次数就可以了。由于数字的范围最大有?10^9109?，所以我们用一个map统计。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

typedeflonglongLL;

signedmain()

{

intn;cinn;

vectorinta(n+1);

mapint,intcnt;

for(inti=1;i=n;i++){

cina[i];

cnt[a[i]]++;

}

intans=0;

for(auto[x,y]:cnt){

if(yx)ans+=y-x;

elseif(yx)ans+=y;

}

coutans;

}