自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:56:26，当前版本为作者最后更新于2024-10-01 00:12:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每次去掉两个中更大的一个数，最后必然剩下 $1$，所以 $h_{n-1}$ 必须为 $1$，否则无解。

$1$ 最多只会被输出两次，即左边删掉的一次和右边删掉的一次。如果有超过两次则也无解。

其它数最多只会被输出一次，因为另一边有一个 $1$ 挡着呢。如果一个非 $1$ 的数被输出两次，则也无解。

无解的情况分析完了，那么怎么构造呢？

注意到刚开始在最两边的数（如果不是 $1$）不会被输出。可以把不出现的的两个数（或者一个数，如果 $1$ 只出现了一次）挑出来，先放到数列的两端。要求字典序最小的方案，则将更小的那个安排在前面。如果只有一个数没被输出，说明 $1$ 在数列的最前面。

接下来按 $h$ 数组顺序安排元素就行。每次判断当前的左右两个数谁更大，再把 $h$ 的新元素放到那边。

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