POJ 1442 Black Box 堆

开始用二叉排序树写的，TLE了，改成优先队列，过了。。

两个版本都贴一下吧，赚稿费。。

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <vector>
 4 using namespace std;
 5 priority_queue<int>qmax;
 6 priority_queue<int, vector<int>, greater<int> >qmin;
 7 
 8 int add[30010];
 9 
10 int main()
11 {
12     int n, m, last = 0, get;
13     scanf("%d %d", &n, &m);
14     for(int i = 0; i < n; i++)
15         scanf("%d", &add[i]);
16     for(int i = 1; i <= m; i++)
17     {
18         scanf("%d", &get);
19         while(last < get)
20             qmax.push(add[last++]);
21         while(qmax.size() >= i)
22         {
23             qmin.push(qmax.top());
24             qmax.pop();
25         }
26         qmax.push(qmin.top());
27         qmin.pop();
28         printf("%d
", qmax.top());
29     }
30     return 0;
31 }

优先队列AC

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct node
 5 {
 6     int data;
 7     struct node *left, *right;
 8 };
 9 int add[30010], cnt;
10 
11 void build(struct node *&p, int k)
12 {
13     if(p == NULL)
14     {
15         p = (struct node *)malloc(sizeof(struct node));
16         p->data = k;
17         p->left = p->right = NULL;
18         return;
19     }
20     if(p->data >= k)
21         build(p->left, k);
22     else build(p->right, k);
23 }
24 
25 void seek(struct node *p, int x)
26 {
27     if(p == NULL || cnt > x)return;
28     seek(p->left, x);
29     if(cnt++ == x)
30         printf("%d
", p->data);
31     seek(p->right, x);
32 }
33 
34 int main()
35 {
36     int n, m, last = 0, get;
37     scanf("%d %d", &n, &m);
38     struct node *root = NULL;
39     for(int i = 0; i < n; i++)
40         scanf("%d", &add[i]);
41     for(int i = 1; i <= m; i++)
42     {
43         scanf("%d", &get);
44         while(last < get)
45             build(root, add[last++]);
46         cnt = 1;
47         seek(root, i);
48     }
49     return 0;
50 }

二叉排序树TLE