1 条题解
-
1
#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
- 上传者