题解 | #mex#_牛客博客

不断进行操作： $a_{i} = max(0, a_{i} - mex)$ ,求所有 $a_{i}$ 相等的最小操作次数

显然如果数组中没有0，那么mex = 0，导致 $a_{i} = a_{i} - 0 = a_{i}$ , 所以似乎直接输出 -1

但是如果一开始所有的 $a_{i}$ 都相等的话，那么操作次数为0.

思路一：模拟即可

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);
    if(a[1] == a[n]){
        cout << "0" << endl;
        return 0;
    }
    if(a[1] != 0){
        cout << "-1" << endl;
        return 0;
    }
    int ans = 1, now = 1;
    for(int i = 1; i <= n; i ++){
        if(a[i] < now) continue;
        else if(a[i] == now) now ++;
        else{
            ans ++;
            ans += a[i] - now - 1;
            now = a[i] + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

用now去模拟不断增长的"mex"

思路二：差分的思想：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


signed main(){
    IOS;
    
    int n; cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);
    if(a[1] == a[n]){
        cout << "0" << endl;
        return 0;
    }
    if(a[1] != 0){
        cout << "-1" << endl;
        return 0;
    }
    int ans = 1;
    for(int i = 1; i <= n; i ++){
        if(a[i] - a[i - 1] > 1) ans += (a[i] - a[i - 1] - 1);
    }
    cout << ans << endl;
    return 0;
}

肥肠不错！