首页 > 代码库 > PAT甲题题解-1014. Waiting in Line (30)-模拟,优先级队列
PAT甲题题解-1014. Waiting in Line (30)-模拟,优先级队列
题意:n个窗口,每个窗口可以排m人。有k为顾客需要办理业务,给出了每个客户的办理业务时间。
银行在8点开始服务,如果窗口都排满了,客户就得在黄线外等候。如果有一个窗口用户服务结束,
黄线外的客户就进来一个。如果有多个可选,选窗口id最小的。
输出查询客户的服务结束时间。
如果客户在17点(注意是包括的!!!就在这里被坑了,一开始还以为不包括。。。)或者以后还没开始服务,就输出Sorry
如果已经开始了,无论多长都会继续服务的。
思路:
建立一个优先级队列,存储在黄线之内的所有客户。
对于m*n之前的人,依此往窗口里排队(即优先级队列里)即可。
对于之后的人,从优先级队列里取出结束时间最少的客户,有相同的话则是窗口最小的,
进入他所在的队列。
同时还要建立linetime数组,存储每个窗口排在末尾客户的结束时间。
当窗口j新加进来一个客户,他的起始时间则是linetime[j],结束时间则是linetime[j]+服务时间,同时更新linetime[j]
最后对于查询的客户,如果起始时间>=17:00,则输出Sorry
否则输出对应的结束时间即可,这里方便起见,以分数存储的,所以最后还要转化一下。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <vector> #include <cstring> #include <queue> using namespace std; const int maxn=1000+5; int n,m,k,q; struct Customer{ int line; int start_time=0; int end_time=0; int process_time; bool operator<(const Customer tmp)const{ /* 取队列中最早结束的,如果时间一样,取窗口id最小的 */ if(end_time==tmp.end_time) return line>tmp.line; else return end_time>tmp.end_time; } }cus[maxn]; int query[maxn]; int finish_time[maxn]; int main() { scanf("%d %d %d %d",&n,&m,&k,&q); for(int i=1;i<=k;i++){ scanf("%d",&cus[i].process_time); } for(int i=1;i<=q;i++){ scanf("%d",&query[i]); } priority_queue<Customer>queueline; int cnt=0; Customer tmp; int linetime[maxn]; memset(linetime,0,sizeof(linetime)); //对于前m*n个人,往队列里插即可 for(int i=1;i<=m && cnt<k;i++){ for(int j=0;j<n && cnt<k;j++){ cnt++; tmp.line=j; tmp.start_time=linetime[j]; tmp.end_time=linetime[j]=tmp.start_time+cus[cnt].process_time; cus[cnt].line=j; cus[cnt].start_time=tmp.start_time; cus[cnt].end_time=tmp.end_time; queueline.push(tmp); } } Customer c; for(int i=cnt+1;i<=k;i++){ //取出结束时间最早的 tmp=queueline.top(); queueline.pop(); c.line=tmp.line; c.start_time=linetime[tmp.line]; c.end_time=linetime[tmp.line]=c.start_time+cus[i].process_time; cus[i].line=c.line; cus[i].start_time=c.start_time; cus[i].end_time=c.end_time; queueline.push(c); } int cid; int maxtime=(17-8)*60; for(int i=1;i<=q;i++){ cid=query[i]; ///原来开始的时间包括17:00。。。只要是17:00或者是以后的,就不被服务 ///原来写的是>,结果一部分样例一直没过,还以为自己前面写错了 if(cus[cid].start_time>=maxtime) printf("Sorry\n"); else{ int hour=cus[cid].end_time/60; int minu=cus[cid].end_time%60; printf("%02d:%02d\n",hour+8,minu); } } return 0; }
PAT甲题题解-1014. Waiting in Line (30)-模拟,优先级队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。