1346 - 算法3-7：银行排队

2 6 1 3 4 1 5 3 9 2 13 4 13 3
3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2
2 5 0 6 0 5 0 6 7 1 7 2

0.00
0.29
1.20

Hint

提示：
题目中选择办理的窗口有三个状态，实际上从序号自小到大查找可以最早办理业务的窗口就已经满足上述三个状态了。可以使用数组来模拟列表。
总结：
实际上数组既可以模拟堆栈又可以模拟队列。

Solution C

#include <stdio.h>
#define SIZE 20
typedef struct{
        int ArrivalTime;                
        int Duration;                       
}CustomerType;                               

int windows[SIZE];                                
int total_time;                                
CustomerType customers[200];
int total;

void BankOpen(){
       
        int i;
        for(i=0; i<SIZE; i++){
                windows[i] = 0;               
        }
        total_time = 0;                        
}

void CustomerIn(int total){
        int i = 0;
        while(i < total){                
                scanf("%d%d",&customers[i].ArrivalTime, &customers[i].Duration);
                i++;
        }
}

void Deals(int m, int n){
        
        int i, j;
        int minTimeIndex;       
        for(i=0; i<n; i++){       
                minTimeIndex = 0;
                for(j=1 ;j<m ;j++){                
                        if(windows[minTimeIndex] > windows[j]){
                                minTimeIndex = j;
                        }
                }
                if(windows[minTimeIndex] <= customers[i].ArrivalTime){     
                        windows[minTimeIndex] = customers[i].ArrivalTime + customers[i].Duration;
                }else{
                        total_time += windows[minTimeIndex] - customers[i].ArrivalTime;
                        windows[minTimeIndex] += customers[i].Duration;
                }
        }
}

int main(){

        int m;                
        while(scanf("%d%d",&m ,&total) != EOF){
                BankOpen();                       
                CustomerIn(total);        
                Deals(m, total);                
                printf("%.2lf\n", total_time*1.0/total);                
        }

        return 0;
}

Solution C++

#include <stdio.h>
#define SIZE 20
typedef struct{
	int ArrivalTime;		// 客户到达银行的时间
	int Duration;			// 客户办理业务的所需要的时间
}CustomerType;				// 客户的数据结构

int windows[SIZE];				// 记录 银行窗口当前何时可以接受下一位客户
int total_time;				// 记录用户总共等待的时间
CustomerType customers[200];// 客户到达银行的队列，使用数组来表述队列
int total;					// 记录当前客户的总数，其实就是队列的队尾

void BankOpen(){
	// 银行开门
	int i;
	for(i=0; i<SIZE; i++){
		windows[i] = 0;		// 刚开始窗口一开始都可以接纳客户
	}
	total_time = 0;			// 总等待的时间与客户人数为 0
}

void CustomerIn(int total){
	int i = 0;
	while(i < total){		// 我们将一天中所有的顾客到来的时间和办理业务所需时间读进来
		scanf("%d%d",&customers[i].ArrivalTime, &customers[i].Duration);
		i++;
	}
}

void Deal(int m, int n){
	// m 个窗口办理客户的业务
	int i, j;
	int minTimeIndex;	// 某个时刻，m 个窗口中最快办理完业务的窗口编号
	for(i=0; i<n; i++){	// 依次办理 n 个客户的业务
		minTimeIndex = 0;
		for(j=1 ;j<m ;j++){		// 在 m 个窗口中查找最快办理完业务的编号
			if(windows[minTimeIndex] > windows[j]){
				minTimeIndex = j;
			}
		}
		if(windows[minTimeIndex] <= customers[i].ArrivalTime){
			// 如果客户不需等待
			// 则该窗口可以接待下一位客户的时间为当前客户到达的时间加上办理的时间
			windows[minTimeIndex] = customers[i].ArrivalTime + customers[i].Duration;
		}else{
			// 如果客户需要等待，则总等待时间就会增加
			// 同时该窗口可以接待下一位客户的时间为当前接待时间加上办理所需时间
			total_time += windows[minTimeIndex] - customers[i].ArrivalTime;
			windows[minTimeIndex] += customers[i].Duration;
		}
	}
}

int main(){

	int m;		// 存储窗口数目
	while(scanf("%d%d",&m ,&total) != EOF){
		BankOpen();			// 银行开门
		CustomerIn(total);	// 迎接客户
		Deal(m, total);		// m 个窗口办理 total 个客户的业务
		printf("%.2lf\n", total_time*1.0/total);		// 计算平均等待时间
	}

	return 0;
}