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

题目：

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

题意：

给一个数 n ，然后有n对形如 label/priority 的二元组，用这 n 对二元组建一个treap，对 label 满足二叉搜索树的性质，对 priority 满足堆的性质，然后按 (<left sub−treap><label>/<priority><right sub−treap>) 的形式输出，即中序遍历这棵树，加一些括号

思路：

直接建 treap 肯定可以卡到 O(n2) ，所以可以选择笛卡尔树，先对 label 排序，然后直接建笛卡尔树，然后中序遍历即可

#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; }

另外这题用单调栈也可以做。首先对label排序，然后按priority往左右扩展，扩展到不大于它的地方，加上括号即可。跟HDU1506正好一反，代码懒得写了。。。