HDU 1873 看病要排队

Tag：#hdu1873 #优先队列 #cpp

题目（原网址：http://acm.hdu.edu.cn/showproblem.php?pid=1873）

看病要排队这个是地球人都知道的常识。不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。现在就请你帮助医院模拟这个看病过程。

Input

输入数据包含多组测试，请处理到文件结束。每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。

接下来有N行分别表示发生的事件。

一共有两种事件：

1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)

2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)

Output

对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。

如果该事件时无病人需要诊治，则输出"EMPTY"。

诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。

Sample Input

7

IN 1 1

IN 1 2

OUT 1

OUT 2

IN 2 1

OUT 2

OUT 1

2

IN 1 1

OUT 1

Sample Out

2

EMPTY

3

1

1

本题的要点就在于C++STL库中优先队列（priority_queue)的使用，优先队列的具体内容本文不再阐述，其定义也很简单：优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。想看具体优先队列，可以看这篇文章。

我们正是需要利用优先队列来完成本题，涉及到的优先队列的基本操作有：

empty() 返回队列是否为空队列；

pop() 类似于出队，删除队首元素

top() 返回队首元素，即返回队列中优先级最高的元素

push() 加入一个元素

然后最重要的，就是自定义优先级。自定义的方法有很多种:

//结构体的声明方式（本文解法所用的）
struct node {    
　　int x, y;     
　　friend bool operator < (node a, node b)     
　　{         
　　　　return a.x > b.x;    //结构体中，x小的优先级高     
　　}
};
priority_queue<node>q;   //定义方法
//在该结构中，y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时，最好不要重载”>”，可能会发生编译错误

//常用重载运算符的方式，在类（结构体）外声明
struct cmp {     
　　operator bool ()(int x, int y)     
　　{        
　　　　 return　x > y;　　 // x小的优先级高       //也可以写成其他方式，如： return p[x] > p[y];表示p[i]小的优先级高
　　}
};
priority_queue<int, vector<int>, cmp> q;    //定义方法
//其中，第二个参数为容器类型。第三个参数为比较函数。

这个是在结构体外声明的，如以下代码：

自定义优先级

本文使用的第一块代码的方法，即在结构体内声明友元重载运算符。

具体解法如下，可看代码注释较为详细：

#include<iostream>
#include<string>
#include<queue>

using namespace std;

struct patient
{
    int pri;//记录优先级 10-1
    int id; //病人ID
    /*bool operator<(const patient& p)
    {
        if(pri==p.pri) return p.id < id;
        else return pri < p.pri;
    }
    */
    friend bool operator < (struct patient a,struct patient b)
    {   if(a.pri==b.pri)
            return a.id>b.id;
        else
            return a.pri<b.pri;
    }
};

int main()
{
    int N;

    while(cin >> N)
    {
        int k = 0; //病人编号
        int a,b; //根据题意：a为医生编号，b为病人的优先级
        patient p2in;//最近的一个入住的病人
        patient p2out;//最近一个出院的病人
        string cmd; //分为OUT IN 两种指令
        priority_queue<patient> q[4]; //三个医生，由此构建优先队列组
        while(N--)
        {
            cin>>cmd;

            if(cmd=="IN")
            {
                cin >> a >> b;
                p2in.id = ++k; //为病人记录编号和优先级
                p2in.pri = b;
                q[a].push(p2in);//压入a医生的优先队列之中
                //cout << a << "医生处入住病人" << p2in.id <<"优先级为" << b <<endl;
            }

            if(cmd=="OUT")
            {
                cin >> a;
                if(q[a].empty()) cout << "EMPTY" << endl; //若A医生当前没有病人需要诊治，返回empty
                else            //否则返回优先级最高的病人
                {
                    p2out = q[a].top();//返回队首元素
                    q[a].pop();
                    cout << p2out.id << endl;
                }
            }
        }
    }

    return 0;
}

参考文章：
https://blog.csdn.net/weixin_43325590/article/details/102923834
https://blog.csdn.net/u012860063/article/details/38519517
https://blog.csdn.net/zs120197/article/details/75675134
https://www.cnblogs.com/xzxl/p/7266404.html