题解：CF2224B Zhily and Mex and Max

分析

考虑尽可能把大数放前面，并让每一个数的 mex 尽可能的大。到底先增强 max 还是先增强 mex 呢？手摸一个样例：0 999：

• 若 0 999，则 ans=0+1+999+1=1001
• 若 999 0，则 ans=999+0+999+1=1999

所以先增强 max，那么就直接把最大值放到最前面，所有的数都可以得到最大的 max 贡献。

后面的数怎么排？很容易想到从小到大排，使 mex 逐步增大，进而使贡献更多。维护 mex 可以用 map 标记以前的数，mex 从 0 开始，若 map[mex] 有值，那么 mex++，每次标记后循环处理即可。

然后就会吃一发罚时。这样子会导致部分相同的数不能做出最大贡献，因为当其做贡献时 mex 并没有达到最大。将相同的数只留一个，剩下的放到末尾，则可以在不改变 mex 增加时做出最大贡献。有一种前人栽树后人乘凉的意味。

具体实现也可以用 map，可以参考我的代码，马蜂不好，不一定是最优实现，但对我而言是最好想的。

参考代码

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int a[N];
bool cmp(int x, int y) { return x < y; }
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        map<int, int> mp;
        int mx = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            mx = max(mx, a[i]);
            mp[a[i]]++;
        }

        int pos = 1;
        a[1] = mx;
        mp[mx]--;
        for (auto i : mp) {
            if (i.second == 0) continue;
            pos++;
            a[pos] = i.first;
        }
        for (auto i : mp) {
            if (i.second - 1 <= 0) continue;
            for (int j = 1; j <= i.second - 1; j++) {
                pos++;
                a[pos] = i.first;
            }
        }

        map<int, bool> p;
        int me = 0;
        long long ans = (long long)n * mx;// 注意这里要强制类型转换一下，因为 n*mx 会超过 int. 我因为这个吃了罚时.

        for (int i = 1; i <= n; i++) {
            p[a[i]] = 1;
            while (p.count(me)) me++;
            ans += me;
        }

        cout << ans << endl;
    }
    return 0;
}