C. Ehab and Prefix MEXs (Codeforces Round #649 Div. 2)

問題

https://codeforces.com/contest/1364/problem/C

問題概要

長さnの配列aが与えられる。1 <= i <= nの各iについてを満たすような配列bを構築せよ。

考察

について、に含まれる数字を使うことはできません。先に使ってしまうと、jのときのMEXがになりえないからです。

見方を変えると、で使うことができるのはに含まれていない数字ということになります。

なので、各数字の出現回数を持っておいて、iより後ろで出現しない数字のうちで未使用かつ最も小さいものをで使う、とすればよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        // 数字がaに出現した回数を記録
        cnt[a[i]]++;
    }

    set<int> usable;
    for (int i = 0; i <= n; i++) {
        // aに使われていない数字はbで使うことができる
        if (cnt[i] == 0) usable.emplace(i);
    }

    for (int i = 0; i < n; i++) {
        // 使える数字のうち一番小さいものを採用
        cout << *(usable.begin()) << " ";
        usable.erase(usable.begin());
        // 1つ出現した
        cnt[a[i]]--;
        // これ以降出現しないなら、使用可能となる
        if (cnt[a[i]] == 0) usable.emplace(a[i]);
    }
    cout << endl;
}