链接
捣鼓了一下午。。按堆建树 写完交 返回TLE。。数据不大 感觉不会超了 无奈拿了数据来看什么奇葩数据会超 发现数据跟我输出不一样 看了好久才明白理解错题意了
给出的字符串有两个标签 按前一个来建二叉搜索树 按后一个建堆 搜索树直接排序 然后依次插入右子树 若当前值比前一个的值大 就在与其父亲比较 总之放到合适位置。
这样的树叫笛卡尔树
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 #include<stack> 10 #include<set> 11 #include<string> 12 using namespace std; 13 #define N 50010 14 struct node 15 { 16 int l,r,p,f; 17 char s[15]; 18 void init() 19 { 20 l=r=f=0; 21 } 22 }tr[N]; 23 int g; 24 void build(int u) 25 { 26 int v = u-1; 27 while(tr[u].p>tr[v].p&&v) v = tr[v].f; 28 tr[u].l = tr[v].r; 29 tr[v].r = u; 30 tr[u].f = v; 31 } 32 void solve(int root) 33 { 34 if(tr[root].l) 35 { 36 printf("("); 37 solve(tr[root].l); 38 printf(")"); 39 } 40 printf("%s",tr[root].s); 41 if(tr[root].r) 42 { 43 printf("("); 44 solve(tr[root].r); 45 printf(")"); 46 } 47 } 48 bool cmp(node x,node y) 49 { 50 return strcmp(x.s,y.s)<0; 51 } 52 int main() 53 { 54 // freopen("data8.in","r",stdin); 55 // freopen("data.out","w",stdout); 56 int i,j,k,n; 57 while(scanf("%d",&n)&&n) 58 { 59 int mm = 0,st;g=0; 60 for(i = 1; i <= n ;i++) 61 { 62 scanf("%s",tr[i].s); 63 } 64 sort(tr+1,tr+n+1,cmp); 65 for(i = 1; i <= n ;i++) 66 { 67 for(j = 0; j < strlen(tr[i].s) ; j++) 68 { 69 if(tr[i].s[j]=='/') break; 70 } 71 tr[i].p = atoi(tr[i].s+j+1); 72 if(mm<tr[i].p) 73 { 74 mm = tr[i].p; 75 st = i; 76 } 77 tr[i].init(); 78 } 79 tr[0].r = 1; 80 tr[1].f = 0; 81 for(i = 2; i <= n ;i++) 82 build(i); 83 printf("("); 84 solve(st); 85 printf(")"); 86 puts(""); 87 } 88 return 0; 89 }