7-46 银行排队问题之单队列多窗口服务 (10 分)
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
输入格式:
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。
输出格式:
在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。
输入样例：
9 0 20 1 15 1 61 2 10 10 5 10 3 30 18 31 25 31 2 3
结尾无空行
输出样例：
1. 6.2 17 61 2. 5 3 1
结尾无空行
###感谢浙江财经大学王瑞洲、周甄陶同学修正测试数据！
1.
#include<iostream> using namespace std; const int N=1010,M=20; struct ll{ int t,p;//到达时间，处理时间 }q[N]; int main(){ int l,r,n,k; cin>>n; l=r=0;队列头尾 for(int i=0;i<n;i++){ cin>>q[r].t>>q[r].p; if(q[r].p>60)q[r].p=60; r++; } cin>>k; int sumwait=0,lenwait=0,wait=0;//总的等待时间，最长等待时间，单次等待时间 int sum[M]={0},winnum[M]={0};//完成时间，窗口人数 while(l<r){ int flag=0,minn=99999,imin=0;//标记变量，最快完成时间，最快完成时间下标 for(int i=0;i<k;i++){ if(sum[i]<=q[l].t){//如果队列首位，到达时间比完成时间大，就代表不需要等待 sum[i]=q[l].t+q[l].p; winnum[i]++; flag=1; l++; break; } if(minn>sum[i]){//如果需要等待，就记录各个窗口里面最快完成的那个窗口的完成时间，下标 minn=sum[i]; imin=i; } } if(!flag){ wait=minn-q[l].t;//等待的时间，最快完成的时间减去队列第一个人到达的时间+ if(lenwait<wait)lenwait=wait;//更新对应窗口的完成时间 sumwait+=wait;//求等待时间的和 sum[imin]=minn+q[l].p;//对应窗口完成时间更新 winnum[imin]++;//对应窗口人数++ l++;//队列删除首位 } } int last=0; for(int i=0;i<k;i++)if(last<sum[i])last=sum[i]; printf("%.1lf %d %d\n",1.0*sumwait/n,lenwait,last); for(int i=0;i<k;i++){ if(i!=0)cout<<' '; cout<<winnum[i];//输出各窗口人数 }cout<<endl; return 0; }
#include<iostream> using namespace std; const int N=1005,M=20; struct ll{ int t,p; }q[N]; int main(){ int l,r,n,k; cin>>n; l=r=0; for(int i=0;i<n;i++){ cin>>q[r].t>>q[r].p; if(q[r].p>60)q[r].p=60; r++; } cin>>k; int sumwait=0,lenwait=0,wait=0; int sum[M]={0},winnum[M]={0}; while(l<r){ int flag=0,minn=99999,imin=0; for(int i=0;i<k;i++){ if(sum[i]<=q[l].t){ sum[i]=q[l].t+q[l].p; winnum[i]++; flag=1; l++; break; } if(minn>sum[i]){ minn=sum[i]; imin=i; } } if(!flag){ wait=minn-q[l].t; if(lenwait<wait)lenwait=wait; sumwait+=wait; sum[imin]=minn+q[l].p; winnum[imin]++; l++; } } int last=0; for(int i=0;i<k;i++)if(last<sum[i])last=sum[i]; printf("%.1lf %d %d\n",1.0*sumwait/n,lenwait,last); for(int i=0;i<k;i++){ if(i!=0)cout<<' '; cout<<winnum[i]; }cout<<endl; return 0; }
