HDU 5437 Alisha’s Party (优先队列)——2015 ACM/ICPC Asia Regional Changchun Online

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<queue>
 7 
 8 using namespace std;
 9 
10 struct fri
11 {
12     char name[200];
13     int come,v;
14     bool operator < (const fri& f) const
15     {
16         if(v!=f.v) return v<f.v;
17         else return come>f.come;
18     }    //为了优先队列里的顺序而重载 
19 }f[150000];
20 
21 int c[150000],ans[150000];
22 
23 int main()
24 {
25     int k,m,q,t,p,sum;
26     int T;
27     
28     cin>>T;
29     
30     while(T--)
31     {
32         memset(c,0,sizeof(c));
33         sum=1;
34         cin>>k>>m>>q;
35         for(int i=1;i<=k;++i)
36         {
37             scanf("%s %d",f[i].name,&f[i].v);
38             f[i].come=i;
39         }
40         for(int i=1;i<=m;++i)
41         {
42             scanf("%d %d",&t,&p);
43             c[t]=p;
44         }    //输入顺序不确定，t个人时进行操作 
45         
46         priority_queue<fri> que;
47         for(int i=1;i<=k;++i)    //每来一个人，检查是否开门 
48         {
49             que.push(f[i]);        //来第i个人入队 
50             int n = c[i];    //来了i个人时应出队的n个人进行操作 
51             while(n&&!que.empty())
52             {
53                 ans[sum++]=que.top().come;    //记录出队人的序号，下面用于输出名字 
54                 que.pop();
55                 --n;
56             }
57         }
58         while(!que.empty())        //剩下的人依次出队 
59         {
60             ans[sum++]=que.top().come;
61             que.pop();
62         }
63         
64         while(q--)
65         {
66             int a;
67             scanf("%d",&a);
68             printf("%s",f[ans[a]].name);
69             if(q==0) printf("\n");
70             else printf(" ");
71         }
72     }
73     return 0;
74 }