题解：P10276 [USACO24OPEN] Farmer John's Favorite Permutation B
cff_0102
·
·
题解
每次去掉两个中更大的一个数，最后必然剩下 1，所以 h_{n-1} 必须为 1，否则无解。
其它数最多只会被输出一次，因为另一边有一个 $1$ 挡着呢。如果一个非 $1$ 的数被输出两次，则也无解。
无解的情况分析完了，那么怎么构造呢？
注意到刚开始在最两边的数（如果不是 $1$）不会被输出。可以把不出现的的两个数（或者一个数，如果 $1$ 只出现了一次）挑出来，先放到数列的两端。要求字典序最小的方案，则将更小的那个安排在前面。如果只有一个数没被输出，说明 $1$ 在数列的最前面。
接下来按 $h$ 数组顺序安排元素就行。每次判断当前的左右两个数谁更大，再把 $h$ 的新元素放到那边。
```cpp
#include<bits/stdc++.h>
using namespace std;
int h[100005];
int v[100005];
int a[100005];
bool in[100005];
void mian(){
memset(v,0,sizeof v);
memset(in,0,sizeof in);memset(a,0,sizeof a);memset(h,0,sizeof h);
int n;cin>>n;
for(int i=1;i<=n-1;i++){
cin>>h[i];
v[h[i]]++;
}
if(h[n-1]!=1){
cout<<-1<<endl;return;
}
int x1=0,x2=0;
for(int i=1;i<=n;i++){
if(v[i]==0){
if(x1)x2=i;
else x1=i;
}if(v[i]>1&&i>1||v[i]>2){
cout<<-1<<endl;return;
}
}
if(x1>x2)swap(x1,x2);
if(x1==0)x1=1;
int l=1,r=n;
a[l]=x1;a[r]=x2;
in[x1]=in[x2]=1;
int nw=1;
for(int i=3;i<=n;i++){//这里的 i 是目前填第几个数
if(a[l]>a[r]){
while(in[h[nw]])nw++;
a[++l]=h[nw];
in[h[nw]]=1;
}else{
while(in[h[nw]])nw++;
a[--r]=h[nw];
in[h[nw]]=1;
}
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t--)mian();
return 0;
}
```