18105 银行的叫号顺序
2023-04-18 12:35:38 时间
18105 银行的叫号顺序
时间限制:8000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC
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 }
相关文章
- Linux驱动实践:你知道【字符设备驱动程序】的两种写法吗?
- 【Rust日报】2021-11-13 感谢Rust社区+ LibertyOS 0.7.0
- 【Rust日报】2021-11-14 一个开源的基于Rust和Flutter的Notion替代产品
- 【Rust投稿】Rust语言优点对比C/C++
- 【Rust日报】2021-11-15 SIMD模块 nightly 已可用
- 【Rust日报】2021-11-16 「投票」为Rust标准库添加控制台输入API
- 遇到生产问题,你会慌嘛?
- 解构 TOGAF-2-EA的野心
- 中台夜话20211115
- 记录那些年 Nacos 的坑
- 注意了,ribbon负载均衡器将被替换
- 阻塞与非阻塞客户端
- 某内网域渗透靶场的writeup
- 常规登录框弱口令测试小Tips
- 网络知识:WiFi越用越慢,到底是什么原因?
- PHP 跌出 TIOBE 编程排行榜 Top 10
- 办公技巧:Word批量小技巧,大大提高工作效率
- 使用 CNN 进行句子分类的自然语言处理
- 六年目睹企业间内卷怪现状:爬虫与反爬之战
- Windows 11 又出新招限制三方浏览器