1 条题解

  • 1
    @ 2022-9-7 12:01:57
    #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;
    }
    
    • 1

    信息

    ID
    1423
    时间
    800ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    2
    已通过
    2
    上传者