Binary Search Heap Construction
Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting. A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.
Output
For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (< left sub-treap >< label >/< priority >< right sub-treap >). The sub-treaps are printed recursively, and omitted if leafs.
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
题目类型：笛卡尔树
算法分析：先对输入数据按照key值从小到大排序，然后按照排好序的序列构建一个笛卡尔树，最后直接中序遍历一下即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 5e4 + 66; struct node { int l, r, par; int v; char s[66]; }; node dt[maxn]; void dfs (int rt) { printf ("("); if (dt[rt].l) dfs (dt[rt].l); printf ("%s/%d", dt[rt].s, dt[rt].v); if (dt[rt].r) dfs (dt[rt].r); printf (")"); } void Init () { for (int i = 0; i < maxn; i++) { dt[i].l = dt[i].r = dt[i].par = 0; dt[i].v = INF; } } bool cmp (node a, node b) { return strcmp (a.s, b.s) < 0; } void Insert (int rt) { int i = rt - 1; while (dt[i].v < dt[rt].v) i = dt[i].par; dt[rt].l = dt[i].r; dt[rt].par = i; dt[i].r = rt; } int main() { // CFF; int n; while (scanf ("%d", &n) != EOF) { if (n == 0) break; Init (); for (int i = 1; i <= n; i++) scanf (" %[a-z]/%d", dt[i].s, &dt[i].v); sort (dt + 1, dt + 1 + n, cmp); for (int i = 1; i <= n; i++) Insert (i); dfs (dt[0].r); puts (""); } return 0; } |
- « 上一篇：poj1751
- poj1789：下一篇 »