CF862A题解

joy2010WonderMaker · 2021-03-09 09:56:45 · 题解

喜提最优解，比第二名快了 45ms。优秀的 285ms+0B 的最优解。

先分析题目。题目的意思是给定 n 个数，使最小的没有出现在集合里的数为 x。也就是说，小于 x 的数必须都出现在集合里，而 x 不能出现在集合里。

前置知识：桶。

桶不仅可以来做桶排，而且还可以统计出现次数。

本题中桶的作用：本题需要判断小于 x 和 x 出现的次数。将小于 x 的数每个数都添上一个，也就是是让结果+1。把集合中为 x 的数都去掉，也就是减去 x 在集合中出现的次数。

这样一定很清晰了，大佬们可以到此了，其他人来看一下代码吧。

AC Code:

#include<cstdio>
int b[101],ans;//b数组是统计每个数字出现的次数，从而判断要加几个减几个
int main(){
    int n,x;
    scanf("%d%d",&n,&x);
    int a;
    while(n--){
        scanf("%d",&a);
        b[a]++;//统计
    }
    if(b[x]>0){//如果集合里出现x，则加上x出现的次数
        ans+=b[x];
    }
    for(int i=0;i<=x;i++){
        if(b[i]==0&&i!=x){
            ans++;//如果集合里有小于x的数没有出现，则加上一个数
        }
    }
    printf("%d",ans);//输出
    return 0;
}