歡迎訪問(wèn)~原文出處——博客園-zhouzhendong

去博客園看該題解

---

題目傳送門 - BZOJ1078

---

題意概括

　　斜堆(skew heap)是一種常用的數(shù)據(jù)結(jié)構(gòu)。它也是二叉樹(shù)，且滿足與二叉堆相同的堆性質(zhì)：每個(gè)非根結(jié)點(diǎn)的值都比它父親大。因此在整棵斜堆中，根的值最小。但斜堆不必是平衡的，每個(gè)結(jié)點(diǎn)的左右兒子的大小關(guān)系也沒(méi)有任何規(guī)定。在本題中，斜堆中各個(gè)元素的值均不相同。 在斜堆H中插入新元素X的過(guò)程是遞歸進(jìn)行的：當(dāng)H為空或者X小于H的根結(jié)點(diǎn)時(shí)X變?yōu)樾碌臉?shù)根，而原來(lái)的樹(shù)根（如果有的話）變?yōu)閄的左兒子。當(dāng)X大于H的根結(jié)點(diǎn)時(shí)，H根結(jié)點(diǎn)的兩棵子樹(shù)交換，而X（遞歸）插入到交換后的左子樹(shù)中。 給出一棵斜堆，包含值為0~n的結(jié)點(diǎn)各一次。求一個(gè)結(jié)點(diǎn)序列，使得該斜堆可以通過(guò)在空樹(shù)中依次插入這些結(jié)點(diǎn)得到。如果答案不惟一，輸出字典序最小的解。輸入保證有解。

---

題解

　　看看大佬怎么寫————>http://www.cppblog.com/MatoNo1/archive/2013/03/03/192131.html

---

代碼

#include <cstring> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; const int N=105; int n,root,fa[N],son[N][2],ans[N]; int main(){scanf("%d",&n);memset(son,-1,sizeof son);memset(fa,-1,sizeof fa);for (int i=1,a;i<=n;i++){scanf("%d",&a);if (a<100)fa[i]=a,son[a][0]=i;elsefa[i]=a-100,son[a-100][1]=i;}root=0;for (int i=n;i>=0;i--){int now=root;while (son[now][1]!=-1)now=son[now][0];int s=son[now][0];if (s!=-1&&son[s][0]==-1&&son[s][1]==-1)now=s;ans[i]=now;if (now==root){root=son[now][0],fa[root]=-1;continue;}s=son[now][0];if (s!=-1)fa[s]=fa[now];son[fa[now]][0]=s;for (s=fa[now];s!=-1;s=fa[s])swap(son[s][0],son[s][1]);fa[now]=son[now][0]=son[now][1]=-1;}for (int i=0;i<=n;i++)printf("%d ",ans[i]);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1078.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1078 [SCOI2008]斜堆 堆的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。