sdut2355Binary Search Heap Construction

捣鼓了一下午。。按堆建树写完交返回TLE。。数据不大感觉不会超了无奈拿了数据来看什么奇葩数据会超发现数据跟我输出不一样看了好久才明白理解错题意了

给出的字符串有两个标签按前一个来建二叉搜索树按后一个建堆搜索树直接排序然后依次插入右子树若当前值比前一个的值大就在与其父亲比较总之放到合适位置。

这样的树叫笛卡尔树

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<stack>

 #include<set>

 #include<string>

 using namespace std;

 #define N 50010

 struct node

 {

     int l,r,p,f;

     char s[];

     void init()

     {

         l=r=f=;

     }

 }tr[N];

 int g;

 void build(int u)

 {

     int v = u-;

     while(tr[u].p>tr[v].p&&v) v = tr[v].f;

     tr[u].l = tr[v].r;

     tr[v].r = u;

     tr[u].f = v;

 }

 void solve(int root)

 {

     if(tr[root].l)

     {

         printf("(");

         solve(tr[root].l);

         printf(")");

     }

     printf("%s",tr[root].s);

     if(tr[root].r)

     {

         printf("(");

         solve(tr[root].r);

         printf(")");

     }

 }

 bool cmp(node x,node y)

 {

     return strcmp(x.s,y.s)<;

 }

 int main()

 {

    // freopen("data8.in","r",stdin);

    // freopen("data.out","w",stdout);

     int i,j,k,n;

     while(scanf("%d",&n)&&n)

     {

         int mm = ,st;g=;

         for(i = ; i <= n ;i++)

         {

             scanf("%s",tr[i].s);

         }

         sort(tr+,tr+n+,cmp);

         for(i = ; i <= n ;i++)

         {

             for(j = ; j < strlen(tr[i].s) ; j++)

             {

                 if(tr[i].s[j]=='/') break;

             }

             tr[i].p = atoi(tr[i].s+j+);

             if(mm<tr[i].p)

             {

                 mm = tr[i].p;

                 st = i;

             }

             tr[i].init();

         }

         tr[].r = ;

         tr[].f = ;

         for(i = ; i <= n ;i++)

         build(i);

         printf("(");

         solve(st);

         printf(")");

         puts("");

     }

     return ;

 }

巴特西

sdut2355Binary Search Heap Construction

最新文章

热门文章