POJ1785(笛卡尔树的构造)
题目：http://poj.org/problem?id=1785
题意：构造笛卡尔树，这里是最大堆构造，然后以广义表的形式输出这棵笛卡尔树。
#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>using namespace std;const int N=500010;const int INF=~0U>>1;struct node{ int fix; int pre,l,r; char str[10]; void clear() { pre=l=r=0; } bool operator < (node t) const { return strcmp(str,t.str)<0; }};node T[N];void Init(int n){ for(int i=0; i<=n; i++) T[i].clear(); T[0].fix=INF;}int Build(int n){ for(int i=1; i<=n; i++) { int j=i-1; while(T[j].fix<T[i].fix) j=T[j].pre; T[i].l=T[j].r; T[j].r=i; T[i].pre=j; } return T[0].r;}void dfs(int cur){ if(cur==0) return; printf("("); dfs(T[cur].l); printf("%s/%d",T[cur].str,T[cur].fix); dfs(T[cur].r); printf(")");}int main(){ int n; char str[105]; while(scanf("%d",&n),n) { Init(n); for(int i=1; i<=n; i++) { scanf("%s",str); sscanf(str,"%[^/]/%d",T[i].str,&T[i].fix); } sort(T+1,T+n+1); int root=Build(n); dfs(root); puts(""); } return 0;}