SDUT 1232 / POJ 1785 Binary Search Heap Construction

发布时间:2016-12-8 19:52:07 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SDUT 1232 / POJ 1785 Binary Search Heap Construction",主要涉及到SDUT 1232 / POJ 1785 Binary Search Heap Construction方面的内容,对于SDUT 1232 / POJ 1785 Binary Search Heap Construction感兴趣的同学可以参考一下。

最近总是不在状态,满脑子都是有的没的,感觉乱糟糟的。计划也越来越难了,做起来各种力不从心。好像整个人已经走在失控的边缘了。笑里春秋多少泪。唉。 好了,下面扯题。 给出N对字符串和数字,然后建树。要求字符串符合排序二叉树,数字符合堆性质。然后按照中序遍历顺序输出。 好了,思路已经很明确了,明显的Treap。以前做过一个询问区间第K大的数的题,貌似这种数据结构可以胜任,可是宝哥给我推荐了划分树. . . . . .当时也是偷懒就只看了一下概念,然后今天周赛果断做不出来啦。 下午写了一个链表的,果断TLE。然后改成树状数组,还是TLE。然后无耻的到后台要来了测试数据. . . 本地竟然跑了4000ms+。然后按权值升序排列竟然只用了300ms就过了。 然后那数据测了一下Treap的效率。如果不按堆的规则维护权值,大约需要13S才能完成建树。按堆维护后需要4S。还是蛮快的。即使代码写的很挫。 #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; struct N { int l,r; bool mark; char s[11]; int p,Size; }tree[50010]; struct P { char s[11]; int p; }node[50010]; int Top; void Insert(int root,char *s,int p) { if(tree[root].mark == false) { tree[root].l = -1; tree[root].r = -1; tree[root].mark = true; tree[root].p = p; strcpy(tree[root].s,s); return ; } if(0 > strcmp(tree[root].s,s)) { if(tree[root].r == -1) { tree[root].r = Top; tree[Top++].mark = false; } Insert(tree[root].r,s,p); if(tree[root].p < tree[tree[root].r].p) { int x = tree[root].r,y = root; N temp; strcpy(temp.s,tree[y].s); temp.p = tree[y].p; strcpy(tree[y].s,tree[x].s); tree[y].p = tree[x].p; strcpy(tree[x].s,temp.s); tree[x].p = temp.p; tree[y].r = tree[x].r; tree[x].r = tree[x].l; tree[x].l = tree[y].l; tree[y].l = x; } } else { if(tree[root].l == -1) { tree[root].l = Top; tree[Top++].mark = false; } Insert(tree[root].l,s,p); if(tree[root].p < tree[tree[root].l].p) { int x = tree[root].l,y = root; N temp; strcpy(temp.s,tree[y].s); temp.p = tree[y].p; strcpy(tree[y].s,tree[x].s); tree[y].p = tree[x].p; strcpy(tree[x].s,temp.s); tree[x].p = temp.p; tree[y].l = tree[x].l; tree[x].l = tree[x].r; tree[x].r = tree[y].r; tree[y].r = x; } } } void Output(int root) { if(root == -1) return ; printf("("); Output(tree[root].l); printf("%s/%d",tree[root].s,tree[root].p); Output(tree[root].r); printf(")"); } bool cmp(P n1, P n2) { return n1.p < n2.p; } int main() { //freopen("data1.in","r",stdin); //freopen("data2.out","w",stdout); int n,i,j; char s[30]; int p; while(scanf("%d",&n) && n) { tree[1].mark = false; Top = 2; for(i = 0;i < n; ++i) { scanf(" %s",s); for(j = 0;s[j] != '/'; ++j) ; s[j] = '\0'; for(++j,p = 0;s[j] != '\0'; ++j) { p += s[j]-'0'; p *= 10; } p /= 10; strcpy(node[i].s,s); node[i].p = p; } sort(node,node+n,cmp); for(i = 0;i < n; ++i) Insert(1,node[i].s,node[i].p); Output(1); printf("\n"); } return 0; }

上一篇:tiny6410裸机实验第1章--------------ARM汇编和编程基础(C与ARM汇编混合编程)
下一篇:胖子哥的大数据之路(五)- 数据资源-垄断的壁垒

相关文章

相关评论