游客 注册 | 登录
中文 | En

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

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。

每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？

题目输入

有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。

题目输出

平均等待的时间，保留两位小数。

输入/输出样例

输入格式

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

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;
}

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;
}

Java解答

import java.util.*;
public class Main 
{
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		int a,b,m,total,c=0,cm,ta;
		double result=0;
		while(cin.hasNext())
		{
			m=cin.nextInt();
			result=0;
			c=ta=0;
			int d[]=new int[m];
			for(int i=0;i<m;i++)
				d[i]=0;
			total=cin.nextInt();
			for(int i=0;i<total;i++)
			{
				a=cin.nextInt();
				cm=25;
				for(int j=0;j<m;j++)
				{
					d[j]=d[j]-(a-ta);
					if(d[j]<cm)
					{
						cm=d[j];
						c=j;
					}
				}
				b=cin.nextInt();
				if(d[c]<1)
				{
					d[c]=b;
				}
				else
				{
					result=result+d[c];
					d[c]=d[c]+b;
				}
				ta=a;
			}
			System.out.printf("%.2f\n",result/total);
		}
		cin.close();
	}
}
请先登陆