题解：CF2224B Zhily and Mex and Max

Algorithm_Killer · 2026-05-07 07:56:36 · 题解

首先观察到数组中最大值对答案的影响是最大的，所以把最大值放在数组的最前面一定是最优的。

接着考虑剩下的数，现在我们要让 \operatorname{mex} 尽可能的大，就要让新放进去的数有意义且最优，所以把剩下的数都从小到大排序，接着扫一遍，如果这个数之前出现过，那么它对 \operatorname{mex} 是没有任何贡献的，统计这种数的出现次数，最后这些数的贡献都是数组当前的 \operatorname{mex}，做完了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define dgd priority_queue<int>
#define xgd priority_queue<int,vecotr<int>,greater<int> >
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define nl cout << "\n"
const int INF=1e9;
const ll Inf=4e18;
const int abc=26;
const double pi=3.1415926;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    return x*f;
}
ll n,r,top,ans,a[200010]; 
map<int,int> mp;
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1,a+n+1);
    ans=n*a[n];mp[a[n]]++;
    while(mp[r]) r++;ans+=r;
    for(int i=1;i<=n-1;i++){
        if(mp[a[i]]) top++;
        else{
            mp[a[i]]++;
            while(mp[r]) r++;
            ans+=r;
        }
    }
    ans+=top*r;
    cout << ans;
    for(int i=1;i<=n;i++) mp[a[i]]=0;
    r=top=0;
    cout << "\n";
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(0),cin.tie(0);
    int t=1;
    cin >> t;
    while(t--) solve();
    return 0;
}