mex - 题解

标签与难度

标签: 贪心, 排序, 数学, 构造, 思维题, 集合难度: 1600

题目大意喵~

Nyahello~ 各位算法大师们好呀！咱是乃爱的我，最喜欢的就是解决各种有趣的谜题啦！今天我们遇到的这个题目是这样的说：

给你一个有 $n$ 个非负整数的数组 $a$ 。我们可以对它进行一轮又一轮的“魔法”操作：

首先，找到当前数组里所有数字的 mex 值。mex 就是指没在数组里出现过的、最小的非负整数。比如说，{1, 2, 3} 的 mex 就是 0，而 {0, 2, 5} 的 mex 就是 1 呐。
然后，把数组里的每一个数 $a_i$ 都减去这个 mex 值。如果减完成负数了，就让它等于 0。公式就是 $a_i := \max\{0, a_i - \text{mex}\}$ 。

我们的任务是，计算出最少需要多少轮这样的操作，才能让数组里所有的数都变得一模一样。如果无论如何都做不到，就要告诉小牛，输出 -1，喵~

解题思路分析

这道题看起来像是在不断地变换数组，有点让人眼花缭乱呢。不过别担心，跟着我的思路，一步步解开它的神秘面纱吧，喵！

第一步：抓住关键的“小尾巴”——特殊情况

在猛扑向问题核心之前，我们先像猫猫一样，小心地检查一下周围有没有陷阱，也就是处理一些特殊情况，的说。

已经完成的情况：如果一开始数组里所有的数就已经相同了，那我们什么都不用做呀！直接甩给他一个 0，表示 0 轮操作，完美收工，喵~
不可能的情况：操作的核心是减去 mex。如果数组里连 0 都没有，那 mex 是多少呢？根据定义，最小的没出现的非负整数就是 0！所以 mex 就是 0。那操作就变成了 $a_i := \max\{0, a_i - 0\}$ ，也就是 $a_i$ 根本不变！如果这时候数组里的数还不全相同，那它们就永远也变不成相同的了。就像一只追不到自己尾巴的小猫，永远在原地打转。所以，如果数组中没有 0 并且元素不全相同，就判定为不可能，输出 -1。

第二步：我们的目标是星辰大海...啊不，是全变成0！

好了，排除了特殊情况，我们现在面对的是一个包含 0 且元素不全相同的数组。我们的目标是让所有数都相同。它们最终会变成什么数呢？

由于操作是不断地做减法，数组里的数只会变小或者不变。想让一堆不同的数（比如 0, 5, 10）变成同一个正数（比如 2），几乎是不可能的。因为每一轮减去的 mex 对所有数都是一样的，它们的差值在它们都大于 0 的时候是保持不变的。所以，最现实、也是唯一能达成的目标，就是让所有数都变成 0！

第三步：化繁为简，只看“不同”

mex 的计算只和数组里有哪些不同的数有关，和每个数出现多少次无关。比如 {0, 5, 5, 5} 和 {0, 5} 的 mex 都是 1。所以，我们可以把重复的数字先丢到一边，只研究由数组中所有不重复的数字组成的集合，让问题更清爽！

咱们把这些不重复的数字从小到大排个序，得到一个序列 $u_0, u_1, u_2, \dots, u_k$ 。因为我们已经确定 0 肯定在里面，所以 $u_0 = 0$ 。

第四步：我的直觉——填补“数字之间的空隙”！

现在，最核心的思路来啦！让我们观察这些排好序的独特数字 $0, u_1, u_2, \dots, u_k$ 。比如说，我们有数组 {0, 0, 2, 5}，独特的数字就是 {0, 2, 5}。

在 0 和 2 之间，缺少了数字 1。这是一个大小为 $2 - 0 - 1 = 1$ 的“空隙”。
在 2 和 5 之间，缺少了数字 3, 4。这是一个大小为 $5 - 2 - 1 = 2$ 的“空隙”。

整个过程可以看作是两个阶段：

阶段一：填补空隙 只要我们的数字序列不是像 0, 1, 2, 3... 这样连续的，mex 就会是第一个空缺的数字。

对于 {0, 2, 5}，mex 是 1。操作一次后，集合变成 {0, 1, 4}。看，我们“填补”了 1 这个空隙！
现在是 {0, 1, 4}，mex 是 2。操作一次后，集合变成 {0, 0, 2}，也就是 {0, 2}。
现在是 {0, 2}，mex 是 1。操作一次后，集合变成 {0, 1}。

经过了 3 次操作，我们把 {0, 2, 5} 变成了 {0, 1}。原来的总空隙大小是 $1+2=3$ ，正好用了3次操作！这似乎是一个规律：把一个带有空隙的数字集合，变成一个从0开始的连续数字块（比如 {0, 1, 2}），所需要的操作次数，恰好等于所有空隙大小的总和！

阶段二：最后一击！ 当我们的数字集合变成一个完美的连续块，比如 {0, 1, 2} 时，会发生什么呢？它的 mex 是 3。进行一次操作： $a_i := \max\{0, a_i - 3\}$ 。

0 变成 max(0, 0-3) = 0
1 变成 max(0, 1-3) = 0
2 变成 max(0, 2-3) = 0 砰！只需要一次操作，所有数字就都变成 0 了！

最终的完美公式！

结合上面的发现，总操作次数就是：

\text{总操作数} = (\text{所有空隙大小的总和}) + 1

那个 +1 就是最后把连续块变成全 0 的那一击！

空隙大小怎么算呢？对于排好序的独特数字 $u_0, u_1, \dots, u_k$ ，第 $i$ 个空隙（ $u_{i-1}$ 和 $u_i$ 之间）的大小就是 $u_i - u_{i-1} - 1$ 。我们把所有正的空隙大小加起来就好啦！

所以，我们的算法步骤就是：

检查数组是否已经全相同（0步）。
用一个 set 提取出所有独特的数字。
检查 set 里有没有 0，没有就返回 -1。
遍历排好序的 set，计算 $\sum (u_i - u_{i-1} - 1)$ 。
最终答案就是这个总和再加 1。

是不是一下子就清晰多啦？喵~

代码实现

下面就是我根据这个思路精心编写的代码啦，注释超详细的哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>

// 使用一个乐于助人的我的口吻来写代码和注释，喵~

void solve() {
    int n;
    std::cin >> n;

    // 用 set 来自动处理重复元素并排序，让我们的爪子保持干净~
    std::set<long long> unique_elements;
    for (int i = 0; i < n; ++i) {
        long long val;
        std::cin >> val;
        unique_elements.insert(val);
    }

    // --- 第一步：处理特殊情况 ---

    // 如果独特的元素只有一个，说明它们本来就都一样啦，不需要操作！
    if (unique_elements.size() == 1) {
        std::cout << 0 << std::endl;
        return;
    }

    // 如果里面没有0，mex就永远是0，数组就永远不变。
    // 就像追不到激光笔的光点，永远也达不到目标，呜~
    // *st.begin() 是 set 中最小的元素
    if (unique_elements.find(0) == unique_elements.end()) {
        std::cout << -1 << std::endl;
        return;
    }

    // --- 第二步：计算空隙并得出答案 ---
    
    // 我们需要一个最终的 "最后一击" 操作来把一个连续的序列 {0, 1, ..., k} 变成全0
    // 所以答案至少是 1
    long long operations = 1;
    
    // 我们用一个变量来记住上一个独特的数字是啥
    long long prev_val = 0; // 我们知道 0 肯定在里面

    // 从头开始遍历 set，就像猫猫巡视自己的领地
    auto it = unique_elements.begin();
    // 跳过第一个元素0
    ++it; 
    
    for (; it != unique_elements.end(); ++it) {
        long long current_val = *it;
        // 计算当前数字和上一个数字之间的 "空隙" 有多大
        // 如果 current_val > prev_val + 1，就说明有空隙！
        long long gap_size = current_val - prev_val - 1;
        
        // 把所有空隙的大小加起来，就是我们 "填补空隙" 阶段需要的操作数
        if (gap_size > 0) {
            operations += gap_size;
        }
        
        // 更新 "上一个数字"，准备检查下一个空隙
        prev_val = current_val;
    }

    std::cout << operations << std::endl;
}

int main() {
    // 加速输入输出，让我们的反应像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 我们把 $N$ 个元素插入 std::set 中，每次插入的代价是 $O(\log k)$ ，其中 $k$ 是 set 中当前的元素数量。所以总的插入时间是 $O(N \log N)$ 。之后遍历 set 的时间是 $O(k)$ ，其中 $k \le N$ 。所以，总的时间复杂度由插入 set 的过程主导，为 $O(N \log N)$ ，对于这道题来说非常快啦！
空间复杂度: $O(k)$ 或 $O(N)$ 我们使用了一个 std::set 来存储所有独特的元素。在最坏的情况下，如果所有 $N$ 个元素都不同，set 的大小会是 $N$ 。所以空间复杂度是 $O(N)$ 。

知识点总结

通过解决这道题，我们又学会了好多东西呢，喵~

Mex (Minimum Excluded): 这是一个在组合游戏和一些算法题中常见的概念，记住它的定义——“最小的没出现的非负整数”，很有用哦！
问题简化: 面对复杂的操作，首先思考哪些信息是核心的。此题中，我们发现只需要关注独特的元素集合，问题就变得简单多了。
分析不变量与单调性: 数组元素只会减少（单调性），这引导我们思考最终状态很可能是全 0。
构造与贪心思想: 我们将解题过程分为“填补空隙”和“最终一击”两个阶段，这是一种构造性的解法。每一步都处理最近的“缺陷”（即最小的mex），体现了贪心的思想。
空隙分析 (Gap Analysis): 对排序后的元素序列，分析它们之间的“空隙”是一种很有效的技巧，可以应用在其他类似问题上。
std::set 的妙用: set 能自动去重和排序，是处理这类需要独特、有序元素问题的绝佳工具！

希望这篇题解能帮到你！继续努力，你也能成为算法大师的，喵~！

mex - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：抓住关键的“小尾巴”——特殊情况 ​

第二步：我们的目标是星辰大海...啊不，是全变成0！ ​

第三步：化繁为简，只看“不同” ​

第四步：我的直觉——填补“数字之间的空隙”！ ​

最终的完美公式！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​