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;
}