MENU

Mahmoud and Ehab and the MEX 题解 | ACM

March 16, 2019 • 我爱学习

题目大意给你一个由 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;
  • }
Last Modified: September 8, 2021