题目大意 | 给你一个由 n 整数组成的集合,和一个数字 x 同时定义 MEX:一个集合的 MEX 数就是这个集合中不存在的非负整数中最小的数 例如集合 {0, 2, 4} 中 MEX 数为 1题意要求求出使一个由 n 整数组成的集合的 MEX 数为 X 最少需要加或减几个元素 |
---|---|
输入数据 | 多组数据。对于每组数据: 第一行为正整数 n,表示集合的元素个数。$\leq$n$\leq$100,0$\leq$\leq$100 第二行包括 n 个正整数,集合的内容 |
数据输出 | 对于每组输入,输出一行,包含一个整数,使一个由 n 整数组成的集合的 MEX 数为 X 最少需要加或减几个元素。 |
样例 | 5 3 0 4 5 6 7 1 0 5 0 1 2 3 4 5 0 |
样例输出 | 2 1 0 |
先说我自己的题目分析(大误)
- 拿到题我就开始分析,首先从集合特征开始分析
- 首先讨论比 x 小的数,要确保比 x 小的数都出现在集合中
- 其次讨论集合中出现 x 的情况,当出现 x,将 x 删去。
- 后来我还讨论了数字比 x 大的情况,现在想来真的是脑子短路了
实际上只考虑比 x 小的数和 x 就可以了,比 x 大的数根本不用考虑
因此 AC 代码为:
- #include<stdio.h>
- #include<string.h>
- int main()
- {
- int n,x;
- int count;
- int num[105];
- int temp;
- while(~scanf("%d %d",&n,&x))
- {
- count = 0;
- memset(num,0,sizeof(num));
- for(int i = 0;i < n;i++)
- {
- scanf("%d",&temp);
- num[temp]++;
- }
- for(int i = x-1;i >= 0;i--)
- {
- if(!num[i])
- {
- count++;
- }
- }
- count += num[x];
- printf("%d\n",count);
- }
- return 0;
- }