# ZOJ 2243 &amp; POJ 1785 Binary Search Heap Construction 笛卡尔树 || 单调栈

xiaoxiao2021-02-28  3

### 题目：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1243 http://poj.org/problem?id=1785

### 思路：

#include <bits/stdc++.h> using namespace std; const int N = 50000 + 10, INF = INT_MAX; struct node { char val[100+10]; int pri, fat, son[2]; friend bool operator< (node a, node b) { if(strcmp(a.val, b.val) < 0) return true; else return false; } void init(int _pri, int _fat) { pri = _pri, fat = _fat; son[0] = son[1] = 0; } }tr[N]; int root; int top, stk[N]; int cartesian_build(int n) { top = 0; for(int i = 1; i <= n; i++) { int k = top; while(k > 0 && tr[stk[k-1]].pri < tr[i].pri) k--; if(k != 0) { tr[stk[k-1]].son[1] = i; tr[i].fat = stk[k-1]; } if(k != top) { tr[i].son[0] = stk[k]; tr[stk[k]].fat = i; } stk[k++] = i; top = k; } return stk[0]; } void dfs(int x) { if(! x) return; printf("("); dfs(tr[x].son[0]); printf("%s/%d", tr[x].val, tr[x].pri); dfs(tr[x].son[1]); printf(")"); } int main() { int n; while(scanf("%d", &n), n) { tr[0].init(INF, 0); for(int i = 1; i <= n; i++) { scanf(" %[a-z]/%d", tr[i].val, &tr[i].pri);//这个读入比较有意思 tr[i].init(tr[i].pri, 0); } sort(tr + 1, tr + 1 + n); root = cartesian_build(n); dfs(root); printf("\n"); } return 0; }