自动搬运

查看原文

来自洛谷，原作者为

	潜翎 退役了，谢谢大家

搬运于2025-08-24 21:38:07，当前版本为作者最后更新于2019-06-13 13:53:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实这篇题解只是对另一篇dalao题解经由自己理解的再阐释，侵删致歉啦qwqqqqq

我们使用的方法是：根据数据把堆的形状搞出来，然后我们在这个堆里找最后一个插入的点，然后我们还原这个点插入之前的情况，然后重复此过程，我们就能得到插入序列啦。

现在问题来了，如何找到最后一个插入的点呢？

阅读题目可知，新节点的插入无论如何都是往左子树插入，所以这个节点一定是在根节点一路向左的地方。

至于左右子树交换的操作，是在插入这个节点之前就进行的，所以对这个节点在左子树这个结论没有影响。

然后这个节点要么一路插到底（没儿子），要么是在某个点停下来，使原来在这里的点成为它的左子树，所以这个点一定没有右子树。

好啦，这样我们就可以找到这个点啦。

可是这个点不唯一怎么办？

假设我们找到了点u和相对点u深度更大的点v符合我们的条件。

如果点v仍然具有左子树，那么点v一定比点u先插入。因为若是点u先插入，点v再插入时，点u会和这颗树的右子树进行一次交换，就不符合给定树的形态了。

那么如果有更多点满足上面的条件，我们就选深度最小的。

如果点v没有左子树，那么谁先插入都可以，但是题目中给定的是小根堆，而我们要求方案字典序最小，那么我们认为点u先插入。

注意，我们先记录的点其实是较后插入的点，所以此时先记录点v

好啦，代码奉上。

如果帮助到你，记得点赞哦

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n;
int ch[100][2],fa[100],ans[100];
int main()
{
    int p;
    scanf("%d",&n);
    memset(ch,-1,sizeof(ch));//记得初始化哦 
    fa[0]=-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p);
        if(p<100)
        {
            ch[p][0]=i;
            fa[i]=p;
        }
        else
        {
            ch[p-100][1]=i;
            fa[i]=p-100;
        }
    }
    int rt=0,del,pos;//根，要删的点，指向的位置。 
    for(int i=0;i<=n;i++)
    {
        pos=rt;//从根开始找 
        del=-1;//没找到删除位置 
        while(del==-1)//还没找到可删的呢 
        {
            if(ch[pos][1]==-1) del=pos;//莫得右儿子 
            pos=ch[pos][0];
        }
        if(ch[del][0]!=-1&&ch[ch[del][0]][0]==-1) del=ch[del][0];//字典序大的后删除 
        ans[i]=del;
        if(del==rt) rt=ch[rt][0];//此时一定没有右儿子所以直接赋值就好啦qwq 
        else//做删除的逆向操作，把这个堆还原回去啦qwq 
        {
            ch[fa[del]][0]=ch[del][0];
            if(ch[del][0]!=-1) fa[ch[del][0]]=fa[del];
            pos=fa[del];
            while(pos!=-1)
            {
                swap(ch[pos][0],ch[pos][1]);
                pos=fa[pos];
            }
        } 
    }
    for(int i=n;i>=0;i--) printf("%d ",ans[i]);
    return 0;
}