codeforces 1364 C

原題連結

題意

思路

1.根據題意可知，不可能輸出-1

2.因數組a是非遞減序列，若a[i] != a[i-1],則b[i] = a[i-1] ;

3.a[i]==a[i-1],那麼b[i]可以在[0,n]中未占用的資料中，自小到大，進行選取。

AC代碼

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

const int N=1e6+10;

int n;
int a[N],b[N],vis[N],c[N],index;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[a[i]]++;
    }
    for(int i=n;i>=0;i--){
        if(!vis[i]){
            c[++index]=i;
        }
    }
    a[0]=a[1];
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1]){
            b[i]=a[i-1];
        }else{
            b[i]=c[index--];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}