题解 | mex

这道题目是一道典型的博弈/构造类贪心题，核心在于理解 mex（最小未出现的非负整数）对数组变化的实质影响。

核心思路分析

我们需要通过操作 ai = max(0, ai - mex)让数组中所有元素相等。

情况 A：数组元素已经全部相同

• 此时不需要任何操作，直接输出 0。

情况 B：数组元素不全相同，且数组中没有 0

• 如果数组中没有 0，那么当前的 mex 必然等于 0。
• 执行操作：。
• 这意味着数组永远不会发生变化。既然初始时不相同，操作后也不变，则永远无法相同。
• 输出 -1。

情况 C：数组元素不全相同，且数组中有 0

这是本题的核心。当数组中有 0 时，mex > 0，数组必将逐渐向 0 靠拢，也就是目标要将所有元素变为 0 。

• 规律观察：
• ① 若数组为连续无空缺，此时 。操作一次后，所有数减去 mex 并与 0 取大，全部变为 0。只需 1 轮。
• ② 若数组有空缺（即某些数字没出现），例如 ：若数组为 ：{0，3}。第一轮：mex=1，数组变为{0,2} ；第二轮：mex=1，数组变为 {0,1}连续无空缺的序列；第三轮：mex=2，数组操作一次变为{0,0} 。共 3 轮。
• 总结公式：设数组中的最大值为 max_val，去重后的元素个数为 s.size()。每一个“缺失”的数字都会导致需要额外的一轮操作来让较大的数“滑”下来填补空位。最终需要的轮数公式为：rounds = max_val - (s.size()-1) + 1= max_val - s.size() + 2
• 对于rounds公式的解读：max_val - (s.size()-1)就是填补空位所需要的轮数，也就是空位的数量，最后+1是因为此时空位已被较大数给填满，序列已经变得有序，回到情况C的①状态，这个时候只需要一轮就能将所有数变成 0。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    set<long long>a; // 既能去除没有意义的重复数，又能对s进行升序排序
    long long temp;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        a.insert(temp);
    }
    if (a.size() == 1) {
        cout << 0;
    } else if (a.count(0) == 0) {
        cout << -1;
    } else { // 当满足一般情况时，
        long long max_val = *a.rbegin();
        long long r_count = a.size();

        long long ans = max_val - r_count + 2;
        cout << ans;
    }
}