首页 > 代码库 > PAT-1017 Queueing at Bank (25)
PAT-1017 Queueing at Bank (25)
这道题目是一道模拟题目，题目意思是有n个串口，和一串顾客到达的时间，顾客按先来先服务方式排队，问你这些顾客的平均等待时间是多少？实现：首先把顾客到达顺序记录下来，然后依据到达时间进行排序，k个窗口维护一个数据结构，就是服务的结束时间last，刚开始用end变量，发现提交的时候报错了，估计是系统保留的关键字。每一次从记录里面拿一个人，遍历k个窗口，查看谁的结束时间最早，然后把这个顾客加到这个窗口上，更新结束时间。如此知道最后，分享一下我的测试数据：
7 307:55:00 1617:00:01 207:59:59 1508:01:00 6008:00:00 3008:00:02 208:03:00 104 307:55:00 507:56:00 3008:00:00 3517:00:00 20
这里注意一点就是你的窗口最后结束时间，可能小于顾客到达时间的情况，那么顾客无需等待，窗口的last也应该更新为新的到达时间，而不是上一次的结束时间，这个小bug解决了，就全部A过了。
#include<stdio.h>#include<iostream>#include<string>#include<algorithm>using namespace std;struct Record{ int hh; int mm; int ss; int lapse; bool operator<(const Record & a) const//Struct 小于操作重载时候需加上const { if(hh<a.hh) return true; else if(hh==a.hh) { if(mm<=a.mm) return true; else if(mm==a.mm) { if(ss<=a.ss) return true; } } return false; }};void add(Record & a,int mm){ a.mm+=mm; if(a.mm>=60) { a.mm%=60; a.hh++; }}int sub(const Record & a,const Record & b){ int sum=0; int ss=a.ss,mm=a.mm,hh=a.hh; bool jie=false; if(ss<b.ss) { ss=ss+60; jie=true; } sum=ss-b.ss; if(jie) { mm-=1; jie=false; } if(mm<b.mm) { mm+=60; jie=true; } sum+=(mm-b.mm)*60; if(jie) { hh-=1; jie=false; } sum+=(hh-b.hh)*60*60; return sum;}Record record[10010];Record last[110];int selectWind(int k){ int minIndex=0; Record min=last[0]; for(int i=1;i<k;i++) { if(last[i]<min) { minIndex=i; min=last[i]; } } return minIndex;}void parse(string time,int &hh,int &mm,int &ss){ int a,b; for(int i=0;i<time.length();i++) { a=time[i]-‘0‘; b=time[i+1]-‘0‘; switch(i/3+1) { case 1: hh=a*10+b; break; case 2: mm=a*10+b; break; case 3: ss=a*10+b; break; } i++; i++; }}bool cmp(const Record & a,const Record & b){ if(a.hh<b.hh) return true; else if(a.hh==b.hh) { if(a.mm<b.mm) return true; else if(a.mm==b.mm) { if(a.ss<b.ss) return true; } } return false;}int main(){ int n,k; string time; int lapse; int hh,mm,ss; freopen("1017-in.txt","r",stdin); freopen("1017-out.txt","w",stdout); while(scanf("%d%d",&n,&k)!=EOF) { int count=0; for(int i=0;i<n;i++) { cin>>time>>lapse; parse(time,hh,mm,ss); if(hh>17||(hh==17&&(mm>0||ss>0))) { count++; continue; } record[i-count].hh=hh; record[i-count].mm=mm; record[i-count].ss=ss; record[i-count].lapse=lapse; } sort(record,record+n-count,cmp); /*for(int i=0;i<n-count;i++) { printf("%02d:%02d:%02d %d\n",record[i].hh,record[i].mm,record[i].ss,record[i].lapse); }*/ int num=n-count; int index=0; for(int i=0;i<k;i++) { last[i].hh=8; last[i].mm=0; last[i].ss=0; } int sum=0; for(int i=0;i<num;i++) { index=selectWind(k); if(last[index]<record[i]) last[index]=record[i]; else sum+=sub(last[index],record[i]); //printf("%d\n",sum); printf("before %d:%d:%d\n",last[index].hh,last[index].mm,last[index].ss); add(last[index],record[i].lapse); printf("after %d:%d:%d\n",last[index].hh,last[index].mm,last[index].ss); for(int j=0;j<k;j++) { printf("%d %d %d\n",last[j].hh,last[j].mm,last[j].ss); } printf("====\n"); } //printf("%d\n",sum); printf("%0.1lf\n",sum/((num)*1.0*60)); } return 0;}
PAT-1017 Queueing at Bank (25)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。