[SCOI2008]斜堆

NC20264. [SCOI2008]斜堆

描述

斜堆(skew heap)是一种常用的数据结构。它也是二叉树，且满足与二叉堆相同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。

但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题中，斜堆中各个元素的值均不相同。在斜堆H中插入新元素X的过程是递归进行的：

当H为空或者X 小于H的根结点时X变为新的树根，而原来的树根（如果有的话）变为X的左儿子。

当X大于H的根结点时，H根结点的两棵子树交换，而X（递归）插入到交换后的左子树中。

给出一棵斜堆，包含值为0~n的结点各一次。求一个结点序列，使得该斜堆可以通过在空树中依次插入这些结点得到。如果答案不惟一，输出字典序最小的解。输入保证有解。

输入描述

第一行包含一个整数n。
第二行包含n个整数d₁, d₂, ... , d_n， d_i < 100表示i是d_i的左儿子，d_i ≥ 100表示i 是d_i-100的右儿子。
显然0总是根，所以输入中不含d₀。

输出描述

仅一行，包含n+1整数，即字典序最小的插入序列。

示例1

输入:

6
100 0 101 102 1 2

输出:

0 1 2 3 4 5 6

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2019-03-16 12:02:51

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define inf 1000000000
using namespace std;
int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,top,root;
int ls[105],rs[105],fa[105],ans[105];
void solve()
{
	int x=root;
	while(rs[x]!=-1)x=ls[x];
	int t=ls[x];
	if(t!=-1&&ls[t]==-1&&rs[t]==-1)x=t;
	ans[++top]=x;
	if(x==root)root=ls[root];
	int f=fa[x];
	if(f!=-1)ls[f]=ls[x],fa[ls[f]]=f;
	while(f!=-1)swap(ls[f],rs[f]),f=fa[f];
}
int main()
{
	fa[0]=-1;
	memset(ls,-1,sizeof(ls));
	memset(rs,-1,sizeof(rs));
	n=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		if(x<100)ls[x]=i,fa[i]=x;
		else rs[x-100]=i,fa[i]=x-100;
	}
	for(int i=1;i<=n+1;i++)
		solve();
	while(top)printf("%d ",ans[top--]);
	return 0;
}