描述

医院中病人需排队挂号看病；有三类号普通号，军人优先号，老人优先号，急诊优先号；

优先级为：急诊优先号 类型为1；>老人优先号，类型为2>军人优先号，类型为3>普通号类型为4;同一类型的号按序看病；

病人挂号的码为：类型码 序号；

病人来了用IN, 病人走了用OUT;

现病人来的顺序如下，请写出病人看好病离开的顺序。

输入

来了的病人挂号的码为：IN 类型码 序号；

看好了用OUT;

输出

看好病的号码

样例输入

IN 4 1
OUT
IN 1 3
IN 2 1
IN 4 2
IN 3 2
OUT
IN 1 1
OUT
IN 2 2
IN 4 3
IN 3 1
OUT
OUT
OUT
OUT
IN 4 4
OUT
OUT
OUT

样例输出

4 1
1 3
1 1
2 1
2 2
3 1
3 2
4 2
4 3
4 4

思路

下面将用2中不同的数据结构去解决次问题
第1中用优先队列，第2中用vector
区别：优先队列的方法要注意运算符的重载，vector的方法在out操作时要对他进行排序

code（优先队列）

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
struct node{
    int priority,id;
};
bool operator < (const node &a,const node &b){
    if(a.priority == b.priority) return a.id>b.id;//id小的优先级高 
    return a.priority  > b.priority;//类型码小的优先级高 
}
int main()
{
    int n;
    priority_queue <node> q;
    string cz;
    while(cin>>cz){
        if(cz=="IN"){
            node patient;
            cin>>patient.priority>>patient.id;
            //注意在加入队列中要用node patient 
            q.push(patient);
        }
        else{
            node patient = q.top();
            q.pop();
            cout<<patient.priority<<" "<<patient.id<<endl;
        }
    }
    return 0;
}

code（vector）

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
struct node{
    int priority,id;
};
bool cmp(const node& a,const node& b){
    if(a.priority==b.priority) return a.id < b.id;
    return a.priority < b.priority;//急诊优先号小的放前面 
}
int main()
{
    int n;
    vector <node> vc;
    string cz;
    while(cin>>cz){
        if(cz=="IN"){
            node patient;
            cin>>patient.priority>>patient.id;
            //注意在加入队列中要用node patient 
            vc.push_back(patient);
        }
        else{
            sort(vc.begin(),vc.end(),cmp);//排序  
            node patient = vc.front();
            vc.erase(vc.begin());//病人看好病离开 
            cout<<patient.priority<<" "<<patient.id<<endl;
        }
    }
    return 0;
}