定义:一个序列中未出现的最小非负数

下面是维基百科和对应机翻:

What’s Mex?

In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name “mex” is shorthand for “minimum excluded” value.

Beyond sets, subclasses of well-ordered classes have minimum excluded values. Minimum excluded values of subclasses of the ordinal numbers are used in combinatorial game theory to assign nim-values to impartial games. According to the Sprague–Grundy theorem, the nim-value of a game position is the minimum excluded value of the class of values of the positions that can be reached in a single move from the given position.

Minimum excluded values are also used in graph theory, in greedy coloring algorithms. These algorithms typically choose an ordering of the vertices of a graph and choose a numbering of the available vertex colors. They then consider the vertices in order, for each vertex choosing its color to be the minimum excluded value of the set of colors already assigned to its neighbors.

在数学中，良序集合的子集的mex是整个集合中不属于该子集的最小值。也就是说，它是补集的最小值。名称“mex”是“最小排除值” 的简写。

除了集合之外，有序类的子类具有最小排除值。序数子类的最小排除值在组合博弈论中用于将nim 值分配给不偏不倚的博弈。根据Sprague-Grundy定理，游戏位置的nim值是从给定位置单次移动可以达到的位置值类别的最小排除值。

最小排除值(Minimum excluded values)也用于图论，贪心着色算法。这些算法通常选择图形顶点的顺序并选择可用顶点颜色的编号。然后他们按顺序考虑顶点，每个顶点选择其颜色作为已分配给其邻居的颜色集的最小排除值

主要用于图论与贪心，对一个序列暴力求Mex可以遍历

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cout << "Our Mex is ";

  int n; cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  sort(a.begin(), a.end());

  if (a.front() == 0)
  {
    int pos = 0;
    while (pos + 1 < n && (a[pos + 1] == a[pos] + 1 || a[pos + 1] == a[pos]))
    {
      pos ++;
    }
    cout << a[pos] + 1 << "\n";
  }
  else cout << a.front() - 1 << "\n";
  return 0;
}