Description

银行的叫号过程是一个优先队列的典型应用，假设，银行有4类客户，分别用优先级1，2，3，4表示，级别越高
则更优先得到服务，例如，当前有三个人排队，两个1级客户，一个3级客户，则银行叫号时，3级客户将先得到服务
，即使另两个1级有客户比他先到。当多个同级的客户将获得服务时，由先到的客户先得到服务。

假设，银行只有一个服务窗口，一次只能服务一个客户，假设该窗口每5分钟服务一个客户，即叫号的时刻分别
为0分钟、5分钟、10分钟、.....如果在叫号的时侯，没有客户，银行职员会去喝杯咖啡或上个洗手间，5分钟后
再继续叫号。

银行给出一系列客户到来的记录，每条记录包括“客户到来的时”，“客户等级”，“客户姓名”（由一个单词构成），请输
出银行服务的客户的顺序。

输入格式

第一数字是客户的数量n（n<=100000）
此后，每一行是一个客户来访信息，包括3个数字，到来的时刻（分钟整点,最大10的8次方）、等级、姓名（最多20个字母）
（已经按到来时刻排序）

输出格式

按服务的先后顺序输出客户的姓名

输入样例

4
0 1 John
3 1 Smith
3 1 Tom
4 2 Flod

输出样例

John
Flod
Smith
Tom

用优先队列做的一道典型题....(给陈老大这题在机房坑了一个中午....)...要说题目哪里有坑的话，注意下第一个顾客不一定在第一次叫号时(0时刻)来的
　　　　其他详情见代码注释：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<utility>
 6 #include<vector>
 7 #define MAX 100000
 8 using namespace std;
 9 
10 int n;
11 typedef struct a
12 {
13     int vip,time;
14     char name[21];
15 } cus;
16 cus people[MAX+5];
17 struct cmp  //比较函数，确定优先队列中元素的权值大小
18 {
19     bool operator() (const cus a,const cus b) const
20     {                    //vip等级大的优先，如果等级相同就比较时间
21         if(a.vip!=b.vip)
22             return a.vip<b.vip;
23         else                   //事实上可以不比较时间的...
24             return a.time<b.time;
25     }
26 };
27 int main()
28 {
29     queue<cus> q;
30     priority_queue<a,vector<a>,cmp> pq;
31     scanf("%d",&n);
32     cus temp;
33     for(int i=0; i<n; i++) //先讲所有顾客按顺序压入普通队列中
34     {
35         scanf("%d%d%s",&temp.time,&temp.vip,temp.name);
36         temp.vip=temp.vip*MAX-i;
37         q.push(temp);
38     }
39     int cnt=0,next_cnt;
40     while(!q.empty())
41     {
42         while(!q.empty()&&(q.front().time+4)/5<=cnt)//cnt为最近的一次叫号点，将能在该点或这之前出现顾客压入优先队列
43         {
44             pq.push(q.front());
45             q.pop();
46         }
47         if(!q.empty())
48             next_cnt=(q.front().time+4)/5;
49         else
50             break;
51         while(!pq.empty()&&cnt<next_cnt) //把 在下个叫号点且有顾客来的时刻前能完成服务 的顾客 弹出
52         {
53             printf("%s
",pq.top().name);
54             pq.pop();
55             cnt++;
56         }
57         cnt=next_cnt;
58     }
59     //
60     while(!pq.empty()) //将剩下的顾客弹出
61     {
62         printf("%s
",pq.top().name);
63         pq.pop();
64     }
65     return 0;
66 }