看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。
Input
输入数据包含多组测试，请处理到文件结束。
每组数据第一行有一个正整数N（0
接下来有N行分别表示发生的事件。
一共有两种事件：
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。（0
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。（0
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 Output
2
EMPTY
3
1
1
源代码：
01.#include <iostream>
02.#include <cstdio>
03.#include <cstring>
04.#include <algorithm>
05.#include <queue>
06.using namespace std;
07.// Accepted 1873 156MS 328K C++(www.cppentry.com) Achiberx
08.struct node {
09. int id;
10. int p; ///priority;
11. bool operator < （const node &a） const {
12. if（a.p == p） return a.id < id;
13. else {
14. return a.p > p;
15. }
16. }
17.};
18.priority_queue<node> Q1, Q2, Q3;
19.
20.char mark ;
21.int index = 1;
22.
23.void init（） {
24. index = 1;
25. memset（mark, '0', sizeof（mark））；
26. while（！Q1.empty（）） Q1.pop（）；
27. while（！Q2.empty（）） Q2.pop（）；
28. while（！Q3.empty（）） Q3.pop（）；
29.}
30.
31.int main（）
32.{
33. int n;
34. int p, d;/// priority, doctor;
35. node tmp;
36. while（scanf（"%d", &n） != EOF） {
37. init（）；
38. for（int i = 0; i < n; i++） {
39. scanf（"%s", mark）；
40. if（mark[0]=='I'） {
41. scanf（"%d%d", &d, &p）；
42. tmp.id = index++;
43. tmp.p = p;
44. if（d==1） {
45. Q1.push（tmp）；
46. continue;
47. }
48. if（d==2） {
49. Q2.push（tmp）；
50. continue;
51. }
52. if（d==3）{
53. Q3.push（tmp）；
54. continue;
55. }
56. }
57. else {
58. int res; ///result
59. bool flag = false; ///is queue empty
60. scanf（"%d", &d）；
61. if（d==1） {
62. if（！Q1.empty（）） {
63. flag = true;
64. tmp = Q1.top（）；
65. Q1.pop（）；
66. res = tmp.id;
67. }
68. }
69. if（d==2） {
70. if（！Q2.empty（）） {
71. flag = true;
72. tmp = Q2.top（）；
73. Q2.pop（）；
74. res = tmp.id;
75. }
76. }
77. if（d==3） {
78. if（！Q3.empty（）） {
79. flag = true;
80. tmp = Q3.top（）；
81. Q3.pop（）；
82. res = tmp.id;
83. }
84. }
85. if（flag） {
86. cout 《 res 《 endl;
87. }
88. else {
89. cout 《 "EMPTY" 《 endl;
90. }
91. }
92. }
93. init（）；
94. }
95. return 0;
96.} |