HDU - 1434 - 幸福列車

題目：

幸福列車

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)

Total Submission(s): 1525    Accepted Submission(s): 421

Problem Description 一批幸福的列車即将從杭州駛向幸福的終點站——溫州，身為總列車長的linle有一些奇怪的癖好。

他會記錄下全部乘客的名字（name）和他們的人品值（RP），根據這些将他們排序，并不時地從某輛列車裡踢出人品最不好（RP值最低）的一個人，當兩個人人品一樣不好時，他就會踢出名字難聽的人（linle認為按字典順序，排在越在後面的人名字越難聽）。

當然出于列車行駛需要，他還會不時的釋出一些指令，比如讓某個乘客上車，合并某兩輛列車等。

linle的上一任秘書***因為不能高效地執行他的這些指令而被炒鱿魚，他現在正在尋覓新的秘書人選，你能不能勝任呢？（謝絕男士，待遇豐厚~~~）  

Input 本題包含多組測試，請處理到檔案結束。

對于每一組測試，第一行包含兩個整數 N ，M ，表示一共有N( N<=10000 ) 輛列車，執行M( M<=10000 )次操作。

接 下來有 N （從1開始記數）輛列車的資訊，每輛列車先有一個數字 Xi(1 <= Xi <= 100 )，表示該列車有Xi個乘客，接下來Xi行乘客資訊，每個乘客包含名字（20個字元以内，不包含空白符）和人品（0<= RP <=30000）。

再接下來有 M 行操作資訊，一共有3種操作，分别為

GETON Xi name RP 表示有一個叫name的人品為RP的人登上第Xi列車

JOIN Xi Xj 表示有将第Xj輛列車合并到Xi輛列車

GETOUT Xi 表示從第Xi輛列車踢出一個人品最差的人

測試資料保證每個操作均合法，即不會将已經被合并到其他列車的列車再進行合并，也不會從一輛空列車裡踢出乘客  

Output 對于每個 GETOUT 指令，輸出被踢出的那個人的名字  

Sample Input 3 5 2 xhd 0 zl 1 2 8600 1 ll 2 1 Ignatius 3 GETOUT 1 JOIN 1 2 GETOUT 1 GETON 3 hoho 2 GETOUT 3   Sample Output xhd zl hoho   Hint Huge input, scanf is recommended.   　　根據題意，隻需要開一個優先隊列的數組，根據題意寫好算子就可以了，然後對于每一種操作都進行相應的模拟即可。   代碼：  

1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 #define MAX 10010
 7 using namespace std;
 8 
 9 typedef struct
10 {
11     string name;
12     int rp;
13 }data;
14 
15 struct cmp
16 {
17     bool operator() (data x,data y)
18     {
19         if(x.rp>y.rp) return 1;
20         else if(x.rp==y.rp && x.name<y.name) return 1;
21         return 0;
22     }
23 };
24 
25 priority_queue<data,vector<data>,cmp> q[MAX];
26 
27 
28 
29 int main()
30 {
31     int i,u,v,t,n,m;
32     data d;
33     string od;
34     //freopen("data.txt","r",stdin);
35     while(scanf("%d %d",&n,&m)!=EOF)
36     {
37         for(i=1;i<=n;i++)
38         {
39             while(!q[i].empty()) q[i].pop();
40             scanf("%d",&t);
41             while(t--)
42             {
43                 cin>>d.name>>d.rp;
44                 q[i].push(d);
45             }
46         }
47         while(m--)
48         {
49             cin>>od;
50             if(od=="GETON")
51             {
52                 cin>>u>>d.name>>d.rp;
53                 q[u].push(d);
54             }
55             else if(od=="JOIN")
56             {
57                 scanf("%d %d",&u,&v);
58                 while(!q[v].empty())
59                 {
60                     q[u].push(q[v].top());
61                     q[v].pop();
62                 }
63             }
64             else
65             {
66                 scanf("%d",&u);
67                 cout<<q[u].top().name<<endl;
68                 q[u].pop();
69             }
70         }
71     }
72     return 0;
73 }      

1434

轉載于:https://www.cnblogs.com/sineatos/p/3302134.html