hdu 5437 优先队列

很容易想到的做法，对于每个询问(a,b)，将a之前的人放入优先队列中，然后pop上b次将答案存下来，注意询问要先按照a的大小排好序。
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 
 8 const int N = 200000;
 9 const int M = 300;
10 char name[N][M];
11 int ans[N];
12 int k, m, q, cnt, pn;
13 
14 struct Node
15 {
16     int id, val;
17     bool operator < ( const Node & o ) const
18     {
19         if ( val != o.val ) return val < o.val;
20         return id > o.id;
21     }
22 } node[N];
23 
24 priority_queue<Node> h;
25 
26 void init()
27 {
28     cnt = 0;
29     pn = 0;
30     while ( !h.empty() ) h.pop();
31 }
32 
33 struct Q
34 {
35     int a, b;
36     bool operator < ( const Q & o ) const
37     {
38         return a < o.a;
39     }
40 } query[N];
41 
42 int main ()
43 {
44     for ( int i = 0; i < N; i++ )
45     {
46         node[i].id = i;
47     }
48     int t;
49     scanf("%d", &t);
50     while ( t-- )
51     {
52         init();
53         scanf("%d%d%d", &k, &m, &q);
54         for ( int i = 0; i < k; i++ )
55         {
56             scanf("%s%d", name[i], &node[i].val);
57         }
58         for ( int i = 0; i < m; i++ )
59         {
60             scanf("%d%d", &query[i].a, &query[i].b);
61         }
62         sort( query, query + m );
63         for ( int i = 0; i < m; i++ )
64         {
65             int a = query[i].a, b = query[i].b;
66             while ( cnt < a )
67             {
68                 h.push( node[cnt] );
69                 cnt++;
70             }
71             for ( int j = 0; j < b && ( !h.empty() ); j++ )
72             {
73                 ans[pn++] = h.top().id;
74                 h.pop();
75             }
76         }
77         while ( cnt < k )
78         {
79             h.push( node[cnt] );
80             cnt++;
81         }
82         while ( !h.empty() )
83         {
84             ans[pn++] = h.top().id;
85             h.pop();
86         }
87         for ( int i = 0; i < q; i++ )
88         {
89             int tn;
90             scanf("%d", &tn);
91             tn--;
92             printf("%s", name[ans[tn]]);
93             if ( i != q - 1 ) putchar(' ');
94             else putchar('
');
95         }
96     }
97     return 0;
98 }