题目翻译
刚开始给你一个空的数组 (b (b_i le 10^6)) , 每次可以将任意一个数填入该数组中 , 但是必须保证第 (i) 次放完后该数组的 ( ext{mex}) 为 (a_i (a_ile 10^5))。请你求出放数字的顺序。若没有合法的顺序就输出 -1 。
数据保证 (a) 数组单调上升。
一个数组的 (mex) 即在这个数组中最小的没有出现过的自然数。
思路
CF 的传统构造题 , 其实很好想。
显然，如果 (a_i>=i) 那显然是没有合法的顺序的，因为如果要使第 (i) 次的 ( ext{mex}=a_i) , 就至少要放 (a_i) 个数 , 而因为 (a_i>=i) , 能放数的位置就会小于 (a_i) , 故一定不合法。
那么我们可以将 (b_i) 分成两种：
- 放置对 (a_i) 有影响的数字。
- 放置对 (a_i) 暂时没有影响的数字。
因为有影响的数字定下来了就无法改变，那么我们可以记录一个指针 (now) ，指向暂时没有影响的 (a_i) 中 (i) 最小的元素。
显然，所填的数一定也是单调递增的，所以还可以在记录一个标记 (num) 表示现在已经填到了数字几。
这样的话我们每读到一个 (a_i) ，就要判断 (num) 是否已经到达了 (a_i-1) ，如果没有就需要将从 (num sim a_i-1) 中的数全部填上。
因为越 (i) 越小，留的余地就越大，所以每当需要填数时，就把他填在 (now) 所指向的位置，并将这个 (b_i) 纳入对 (a_i) 有影响的那一类中。
但是需要注意的点是，当 (a_i) 这个数首次出现时，(b_i) 一定是对 (a_i) 有影响的，因为第 (i) 次填数导致了 (a_i) 的变化。
而那些直到最后也没有对 (a_i) 造成影响的 (b_i) ，我们可以把他们全部设为 (10^6) ，因为 (a_i le 10^5) 而 (b_i le 10^6)，所以填 (10^6)。一定不会对 (a_i) 造成影响。
Code
#include<bits/stdc++.h>
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
const int N=1e5+5;
int n,a[N],b[N],have,num,now=1;
int main()
{
memset(b,-1,sizeof(b));
// 将 b 数组全部设为暂时无影响
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
{
if(a[i]>i)
// 若 a_i > i 则一定无解
{
printf("-1
");
return 0;
}
for(;num<=a[i]-1;++num)
// 将 num ~ a_i-1 里的数全部填上
{
if(b[i]==-1)
// 如果 a_i 首次出现，则 b_i 一定有影响
b[i]=num;
else
{
while(b[now]!=-1)
// 找到暂时没有影响中 i 最小的位置
now++;
// 将这个位置填上；
b[now]=num;
}
}
num=a[i];
}
for(int i=1;i<=n;++i)
if(b[i]==-1) printf("%d ",1000000); // 最后也没有影响的直接输出10^6
else printf("%d ",b[i]);
return 0;
}