数据结构-银行排队 （C语言代码）

解题思路: 

    显然可以用二维数组模拟各窗口各队列，但可将问题简化：

    1、题目数据对应客户先后到来的时间，故可以将队列简化剩队尾，只需记录队尾的人离开的时刻，就可以得到后来者的状态，则使用一维数组即可。

    2、客户先后到达，只需与队尾的人的离开时刻比较：

    ①、若后来者到来的时刻在队尾的人离开时间之后，显然不用等待；

    ②、若后来者到来的时刻在队尾的人离开时间之前，则需要排队，此时等待时间就是队尾的人离开时刻 - 后来者到达时刻。

注意事项:

    1、客户到来会选择空闲时间最长的窗口，即选择队尾的人离开最早的窗口。

    2、每次有客户到来，相应窗口的队尾要更新。

    3、多组测试数据，每次要对窗口队列等数据清0。

    3、题目中的平均等待时间 = 总等待时间 / 总人数。

参考代码:

#include<stdio.h>
#include<string.h>

int p[20]; // 模拟各窗口队列（简化，只有队尾）
double wait;

// 选择窗口 -- 到达时刻 - 停留时间 - 窗口数
void SelectWin(int arri, int stay, int m);

int main()
{
    int i, m, total, arri, stay;
    
    while(scanf("%d", &m) != EOF){
        
        scanf("%d", &total);
        
        memset(p, 0, sizeof(p)); // 多组测试数据，数据重置
        wait = 0;
        
        for(i = 0; i < total; i++){
            
            scanf("%d%d", &arri, &stay);
            SelectWin(arri, stay, m);
        }
        
        wait /= total; // 平均等待时间
        printf("%.2lf\n", wait);
    }
    return 0;
}


void SelectWin(int arri, int stay, int m){
    
    int best = 0;
    
    for(int i = 0; i < m; i++){
        
        if(p[i] < p[best]){
        
            best = i; // 选取最优窗口，空闲时间最长对应窗口队尾的人离开时刻最早
        }
    }
    
    if(arri <= p[best]){ // 在队尾的人离开之前到达，排队等待
    
        wait += p[best] - arri; // 记录等待时间总和
        p[best] = p[best] + stay; // 更新队尾数据
    }
    
    else{ // 不用等待的情况，即没有队尾（队尾的人已经离开）
    
        p[best] = arri + stay; // 更新队尾数据
    }
}