Making Mexes

题意

给定一个长度为 $N$ 的数组，每个数都在 $0..N$ 之间。一次操作可以把任意一个元素改成任意非负整数。

对每个 $i=0,1,\ldots,N$ ，求最少操作多少次，能让数组的 mex 等于 $i$ 。

mex 等于 $i$ 的意思是： $0..i-1$ 都出现过，而 $i$ 没有出现。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:09
 * update_at: 2026-07-11 15:11
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int INF = 1e9;

int n;
int a[MAXN];      // 原数组。
int b[MAXN];      // 枚举出的修改后数组。
int best[MAXN];   // best[mex] 表示得到该 mex 的最少修改次数。

int get_mex() {
    bool seen[MAXN];
    for (int i = 0; i <= n; i++) {
        seen[i] = false;
    }

    for (int i = 1; i <= n; i++) {
        if (0 <= b[i] && b[i] <= n) {
            seen[b[i]] = true;
        }
    }

    for (int i = 0; i <= n; i++) {
        if (!seen[i]) return i;
    }
    return n + 1;
}

int count_changes() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) cnt++;
    }
    return cnt;
}

void dfs(int pos) {
    if (pos == n + 1) {
        int mex = get_mex();
        int changes = count_changes();
        if (0 <= mex && mex <= n && best[mex] > changes) {
            best[mex] = changes;
        }
        return;
    }

    // 小数据暴力：第 pos 个位置枚举修改后的值，0..n 已足够表示所有 mex 结果。
    for (int value = 0; value <= n; value++) {
        b[pos] = value;
        dfs(pos + 1);
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= n; i++) {
        best[i] = INF;
    }

    dfs(1);

    for (int i = 0; i <= n; i++) {
        cout << best[i] << '\n';
    }

    return 0;
}

这个暴力把每个位置最终修改成什么值看成一层选择。递归生成完整的最终数组后，再计算它的 mex 和修改次数。它能直接说明“最少操作数”的含义，但一共有 $(N+1)^N$ 种最终数组，只能用于小数据。

现在考虑目标 mex 为 $i$ 。

要让 mex 等于 $i$ ，必须满足两个条件：

数字 $i$ 不能出现。
数字 $0,1,\ldots,i-1$ 都必须出现。

所以至少要做两类修改：

原数组中等于 $i$ 的元素都要改掉，数量是 cnt[i]。
小于 $i$ 但没有出现的数字都要补出来，数量记为 missing_lt_i。

答案为什么是二者最大值，而不是相加？

因为一次修改可以同时完成两件事：把一个等于 $i$ 的元素改成某个缺失的小于 $i$ 的数。这样既消除了一个不该出现的 $i$ ，又补上了一个必须出现的小值。

如果 cnt[i] 更多，剩下的 $i$ 改成大于 $i$ 的数即可。如果缺失小值更多，剩下的缺失小值用其它可改元素补上即可。

因此：

ans_i=\max(\text{cnt}[i],\text{missing\_lt\_i})

从小到大枚举 $i$ 时，missing_lt_i 可以增量维护。输出当前答案后，如果 cnt[i] == 0，那么数字 $i$ 对之后的目标 mex 来说就是一个缺失小值，所以 missing_lt_i++。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 15:09
 * update_at: 2026-07-11 15:11
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
int cnt[MAXN]; // cnt[x] 表示数值 x 在原数组中出现了多少次。

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    int missing_lt_i = 0; // 0..i-1 中缺失的数的个数。

    for (int i = 0; i <= n; i++) {
        cout << max(cnt[i], missing_lt_i) << '\n';

        if (cnt[i] == 0) {
            missing_lt_i++;
        }
    }

    return 0;
}

复杂度

统计次数和枚举答案都只需要线性扫描。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

mex 题常见的关键是把定义拆开：目标值本身不能出现，目标值之前的所有数必须出现。

本题中“改掉目标值”和“补齐缺失小值”可以由同一次操作同时完成，所以答案取最大值。

目录

题意

思路

代码

复杂度

总结