problem
给定长为 \(n/2\) 的数组 \(b\)，试求出字典序最小的排列 \(p\) 使得 \(b_i=\max_{p_{2i-1},p_{2i}}\)，或者报告无解。\(n\leq 10^5\)。
solution
考虑显然的结论：\(p_{2i}=b_i\)。这时 \(p_{2i-1}<p_{2i}\) 很优。
这时相当于是剩下一些数，要去匹配这些 \(p_{2i}\)。
法一（错误）
考虑构造一组解：从小到大扫，然后匹配遇到的第一个。
然后考虑从值域出发，从小到大将一个更小的值换到前面去。可惜是 \(O(n^2)\) 的。
法二
考虑倒着扫。
因为字典序最小，也等价于大的数字尽量在后面。
维护一个堆，存放可以放的位置，每次拿最大的放。
code
点击查看代码
typedef long long LL;
int n,a[200010],pos[200010];
int mian(){
for(int i=1;i<=n;i++) pos[i]=0;
for(int i=2;i<=n;i+=2) scanf("%d",&a[i]),pos[a[i]]=i-1;
priority_queue<int> q;
for(int i=n;i>=1;i--){
if(pos[i]) q.push(pos[i]);
else{
if(q.empty()) return puts("-1"),0;
a[q.top()]=i,q.pop();
}
}
for(int i=1;i<=n;i++) printf("%d%c",a[i]," \n"[i==n]);
return 0;
}