首页 > 代码库 > BZOJ 1078 斜堆
BZOJ 1078 斜堆
感谢MATO大神的博客 http://www.cppblog.com/MatoNo1/archive/2013/03/03/192131.html
注意细节。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 150using namespace std;int n,x,ls[maxn],rs[maxn],fath[maxn],ans[maxn],root=1;int find(){ int now=root; while (ls[now]) { if (!rs[now]) { if ((!ls[ls[now]]) && (!rs[ls[now]])) now=ls[now]; break; } now=ls[now]; } if (now==root) root=ls[now]; int ret=fath[now];ls[ret]=0;fath[ls[now]]=ret;ls[ret]=ls[now]; while (ret) { swap(ls[ret],rs[ret]); ret=fath[ret]; } return now;}int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&x); if (x>=100) { rs[x-100+1]=i+1; fath[i+1]=x-100+1; } else { ls[x+1]=i+1; fath[i+1]=x+1; } } for (int i=n+1;i>=1;i--) ans[i]=find()-1; for (int i=1;i<=n+1;i++) printf("%d ",ans[i]); return 0;}
BZOJ 1078 斜堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。