1.题目
7-5 银行排队问题之单队列多窗口服务
分数 25
全屏浏览
切换布局
作者 DS课程组
单位 浙江大学
假设银行有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
输出样例：
6.2 17 61
5 3 1
2.分析
判断窗口的完成时间和顾客的到达时间。
当顾客到达时
如果窗口的完成时间大于顾客的到达时间，计算顾客的等待时间并记录最长等待时间。
如果窗口的完成时间小于顾客的大到达时间，那么当顾客到达时窗口肯定是空的，那么就看有几个空的窗口，找出其中编号最小的，记录服务时间。
还有点是，每位顾客事务被处理的最长时间为60分钟。最好在输入时判断。
3.代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX=10000; //定义最大容量
struct People{ //定义顾客结构体
int arrive;
int serval;
}p[MAX];
struct window{ //定义窗口结构体
int id;
int time;
int number;
}w[MAX];
int N,K,uns[MAX],l;
bool cmp(window a,window b){ //比较函数(比较结束时间，结束时间一样则比较窗口号)
if(a.time==b.time){return a.id<b.id;}
return a.time<b.time;
}
bool cmp1(window a,window b){return a.id<b.id;} //比较函数，按窗口号排序
int main(){
int sum=0,ma=0;
cin>>N;
for(int i=0;i<N;i++){
cin>>p[i].arrive>>p[i].serval;
if(p[i].serval>60) //如果服务时间大于60则变成60
p[i].serval=60;
}
cin>>K;
for(int i=0;i<K;i++){w[i].id=i;}
for(int i=0;i<N;i++){
sort(w,w+K,cmp); //按结束时间排序
if(w[0].time>=p[i].arrive){ //窗口结束时间大于顾客到达时间
l=max(l,w[0].time-p[i].arrive); //记录最长等待时间
sum+=w[0].time-p[i].arrive; //记录等待时间和
w[0].time+=p[i].serval; //更新窗口结束时间
w[0].number++;
ma=max(ma,w[0].time); //记录最后结束时间
}
else{ //窗口结束时间小于顾客到达时间
int t=w[0].id;
int index=0;
for(int j=0;j<K;j++){ //找到空闲窗口最小的窗口号
if(w[j].time<=p[i].arrive){
if(w[j].id<t){
t=w[j].id;
index=j;
}
}
}
w[index].time=p[i].arrive; //更新同上
w[index].time+=p[i].serval;
ma=max(w[index].time,ma);
w[index].number++;
}
}
printf("%.1f %d %d\n",sum*1.0/N,l,ma);
sort(w,w+K,cmp1); //按序号排序输出
for(int i=0;i<K;i++){
if(i) cout<<" "<<w[i].number;
else cout<<w[i].number;
}
return 0;
}