CF1364C-Ehab and Prefix MEXs

a[i]<=i，否则当a[i]>i时，需要1~i项有数字0~a[i]-1，这一共是a[i]个数字，而1~i项只有i个数字，需要的比拥有的数字多，不成立

当a[i]!=a[i-1]时，说明Mex改变了，那么需要b[i]为a[i-1]才会改变，所以每个这样的b[i]就已经确定好了

接下来当a[i]=a[i-1]时，例如1 2 2 2 5，对应的b[i]可以分别为b[1]=0 b[2]=1 b[3]=3 b[4]=4 b[5]=2：b[1], b[2], b[5]是根据a[i]!=a[i-1]，所以确定为a[i-1]的值，接下来是b[3]与b[4]的选择理由：

想要Mex值变成5，那意味着b[1]~b[i]需要出现过0~4，所以0~4是这五个数字的填充选择，但是在b[3]与b[4]位置不可以填充2，因为如果b[3]填充2，那么a[3]会变成3，因此，需要在填充选择中，将a[i]出现过的数字删除；而当出现1 2 2 2 5 5 5时，显然0~4这四个数字如果按照将a[i]中数字删除，然后每填充一个就删一个数字的方法的话，那么0~4这四个数字不够，所以采用另一种方式：

初始化num=0, 利用set记录a[i]中出现的数字，当a[i]=a[i-1]时，判断num是否为set中出现过的，没有的话，就说明num可以填充在这个位置；而a[i]!=a[i-1]时，直接填充a[i-1]即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 void solve()
 4 {
 5     int n;
 6     cin>>n;
 7     vector<int> a(n+1), ans;
 8     set<int> buc;
 9     for(int i=1; i<=n; i++){
10         cin>>a[i];
11         if(buc.count(a[i])==0)
12             buc.insert(a[i]);
13     }
14     int num=0;
15     for(int i=1; i<=n; i++){
16         if(i==1 || a[i]==a[i-1]){
17             while(buc.count(num)>0){
18                 ++num;
19             }
20             ans.push_back(num);
21             num++;
22         }else{
23             ans.push_back(a[i-1]);
24         }
25     }
26     for(auto &i:ans){
27         cout<<i<<' ';
28     }
29 }
30 int main(void)
31 {
32     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
33     solve();
34     return 0;
35 }