幸福列车（多个优先队列）

电玩女神 2022-08-01 11:22 207阅读 0赞

# 幸福列车 #

**Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)  
Total Submission(s): 1851    Accepted Submission(s): 554**

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.

Author

linle

Source

[ACM暑期集训队练习赛（四）][ACM]

#include<cstdio>
    #include<iostream>
    #include<queue>
    #include<vector>
    #include<cstring>
    using namespace std;
    struct node
    {
        string name;
        int rp;
    }nd;
    struct cmp
    {
        bool operator () (node a,node b)
        {
            if(a.rp==b.rp)
            {
                return a.name<b.name;//注意这里！对头的name最大！字典序大！
            }
            else
            {
                return a.rp>b.rp;//队头的人品值低
            }
        }
    };
    int main()
    {
        int n,m,i,k,a,b;
        string s,s_cmd;
        priority_queue<node,vector<node>,cmp>p[10010];
        while(cin>>n>>m)
        {
           for(i=1;i<=n;i++)
           {
               while(!p[i].empty())
               {
                   p[i].pop();
               }//清光队列
               cin>>k;
               while(k--)
               {
                   cin>>nd.name>>nd.rp;
                   p[i].push(nd);//p[i]压进来一个元素！
               }
           }
           while(m--)
           {
               cin>>s_cmd;
               if(s_cmd=="GETON")
               {
                   cin>>a;
                   cin>>nd.name>>nd.rp;
                   p[a].push(nd);
               }
               else if(s_cmd=="GETOUT")
               {
                   cin>>a;
                   nd=p[a].top();
                   p[a].pop();
                   cout<<nd.name<<endl;
               }
               else
               {
                   cin>>a>>b;
                   while(!p[b].empty())
                   {
                       p[a].push(p[b].top());
                       p[b].pop();
                   }
               }
           }
        }
    }

**多优先队列问题，挺简单的！**

[ACM]: http://acm.hdu.edu.cn/search.php?field=problem&key=+ACM%CA%EE%C6%DA%BC%AF%D1%B5%B6%D3%C1%B7%CF%B0%C8%FC%A3%A8%CB%C4%A3%A9&source=1&searchmode=source