Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 8383 | Accepted: 2418 |
Description
Input
Output
Sample Input
7 a/7 b/6 c/5 d/4 e/3 f/2 g/1 7 a/1 b/2 c/3 d/4 e/5 f/6 g/7 7 a/3 b/6 c/4 d/7 e/2 f/5 g/1 0
Sample Output
(a/7(b/6(c/5(d/4(e/3(f/2(g/1))))))) (((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7) (((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))
Source
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <cstdlib> #define N 50010 using namespace std; struct num { char label[20]; int val; }a[N]; struct Num { int ch[2]; int val; char label[20]; }b[N]; char s1[20]; int n,stack[N],op[N]; int cmp(const void *p1,const void *p2) { struct num * pt1 = (struct num *)p1; struct num * pt2 = (struct num *)p2; if(strcmp(pt1->label,pt2->label)>0) { return 1; }else { return -1; } } int main() { //freopen("data.txt","r",stdin); int insert(); void find(int k); while(scanf("%d",&n)!=EOF) { if(n==0) { break; } for(int i=1;i<=n;i++) { scanf("%s",s1); int Top=0; int l = strlen(s1); int pos; for(int j=0;j<=l-1;j++) { if(s1[j]==‘/‘) { pos = j; a[i].label[Top]=‘\0‘; break; } a[i].label[Top++] = s1[j]; } int sum = 0; for(int j=pos+1;j<=l-1;j++) { sum = sum*10+s1[j]-‘0‘; } a[i].val = sum; } qsort(a+1,n,sizeof(a[0]),cmp); for(int i=1;i<=n;i++) { b[i].ch[0] = b[i].ch[1] = 0; b[i].val = a[i].val; strcpy(b[i].label,a[i].label); } int head= insert(); find(head); printf("\n"); } return 0; } int insert() { int Top=-1; for(int i=1;i<=n;i++) { int k = Top; while(k!=-1&&a[stack[k]].val<a[i].val) { k--; } if(k!=-1) { op[i] = stack[k]; b[stack[k]].ch[1] = i; } if(k!=Top) { op[stack[k+1]] = i; b[i].ch[0] = stack[k+1]; } Top = k; stack[++Top] = i; } return stack[0]; } void find(int k) { if(k==0) { return ; } printf("("); find(b[k].ch[0]); printf("%s/%d",b[k].label,b[k].val); find(b[k].ch[1]); printf(")"); }
POJ 1785 Binary Search Heap Construction,布布扣,bubuko.com
POJ 1785 Binary Search Heap Construction
原文:http://blog.csdn.net/yongxingao/article/details/19995915