银行排队问题之单队列多窗口服务 (25分)（C语言）

假设银行有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

感谢浙江财经大学王瑞洲、周甄陶同学修正测试数据！

总体思路：某个顾客到达时，从左向右寻找要去办理事务的窗口，若发现有已经办理完或刚好有人办理完，就去此窗口办理，无等待时间。若每个窗口都有人，就选择最早结束的窗口，等待时间就是这个窗口结束时间减去到达时间。

代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct customer{
          
   
    int T,P;
}*cust;

void custQue();
int main()
{
          
   
    custQue();
    return 0;
}
void custQue()
{
          
   
    int wait=0,sumWait =0,MaxWait =0;
    //time[100]数组存放办理时间，即某个窗口办完业务的时间
    //num[100]存放某个窗口的人数
    int time[100]={
          
   0},num[100]={
          
   0},j,maxFin;
    int n,i,m,min,pmin=0;
    cust cu;
    scanf("%d",&n);
    cu = (cust)malloc(sizeof(struct customer)*n);
    for(i=0;i<n;i++)
    {
          
   
        //输入数据时，满60设置为60
        scanf("%d%d",&cu[i].T,&cu[i].P);
        if(cu[i].P>60)
            cu[i].P = 60;
    }
    scanf("%d",&m);

    for(i=0;i<n;i++){
          
   
        //当有多个窗口可选择时，顾客选择编号最小的窗口
        //printf("到达：%d 事务：%d
",cu[i].T,cu[i].P);
        min = time[0];
        pmin = 0;
        for(j=1;j<m;j++){
          
   
            if(min<=cu[i].T){
          
   
                min =  i;
                break;
            }
            if(min>time[j])
            {
          
   
                min = time[j];
                pmin = j;
            }
        }
        //所选窗口事务是否办理完成
        if(time[pmin] < cu[i].T){
          
   
            time[pmin] = cu[i].P+cu[i].T;
            num[pmin]++;
        }else{
          
   
            wait = time[pmin] -cu[i].T;
            if(MaxWait<wait)
                MaxWait = wait;
            sumWait+=wait;
            time[pmin]+= cu[i].P;
            num[pmin]++;
        }
    }
    //寻找最大完成时间
    maxFin = time[0];
    for(i=1;i<m;i++){
          
   
        if(maxFin<time[i])
            maxFin = time[i];
    }
    printf("%.1f %d %d
",1.0*sumWait/n,MaxWait,maxFin);
    for(i=0;i<m;i++){
          
   
        if(!i)
            printf("%d",num[i]);
        else
            printf(" %d",num[i]);
    }
}