2020-11-29

2023-12-19 19:57:51

假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。

输入格式:

输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。

输出格式:

在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。

在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。

输入样例：

输出样例：

6.2 17 61
5 3 1

看到这道题目的时候本能的想到应该使用队列，但是其实并没有用到太多队列的性质。

思路：

首先我使用三个数组： window[11] result[11] cust[1005]

首先我使用数组 window 来保存每个窗口当前处理人的待处理时间，数组 result 记录每个窗口的累计处理人数，每次增加一个人就自加，数组 cust 负责保存用户信息，变量 front负责调用队首元素，变量time相当于一个时间轴，它会一直累加，直到 window和队列都为空，此时说明全部处理完毕，time即为处理的总时间，然后再定义两个变量 MaxWaitTime 和 AllWaitTime 分别保存最长等待时间和总共的等待时间

1、创建用户信息结构

首先我需要创建客户的结构变量，包含 到达时间需处理时间等待时间

struct Customer
{
    int arrive;
    int process;
    int wait;
}cust[1005];

2、数据的输入

然后按照题目要求输入客户的数据，这里要特别注意，每一个顾客的处理时间不超过60分钟，所以对于处理时间大于60分钟的客户，应该把他的时间改成60分钟 （我在一开始的时候认为每个窗口单次最多处理60分钟，时间过了就让客户继续排队，其实不是的，每个人最多允许处理60分钟，超了就不管了，客服只处理60分钟）

	for(int i = 0;i < n;i++)
	{
		scanf("%d %d",&cust[i].arrive,&cust[i].process);	
		if(cust[i].process > 60)cust[i].process = 60;
	}

3、时间轴的累加

这是一个大的循环，每次时间轴 time++,直到所有窗口和队列都为空，此时终止循环

for(time = 0;;time++)
{
    //相关操作
    if(窗口为空 && 队列为空)break;
}

以下为循环中的详细操作

1、window [ ] 的检查

每一次时间轴 time 加一，都需要对 window[ ] 的非零元素进行自减

		for(int j = 0;j < k;j++)
		{
			if(window[j] >= 1)window[j]--;
		}

2、整体等待时间的累加

每一次时间轴 time 加一，此时会对队列中的客户进行检查，如果发现有客户的到达时间比 time 要小，说明此时该客户已经到达了银行，处于等待状态，此时 AllWaitTime ++;

		for(int j = front;j < n;j++)
		{
			if(cust[j].arrive < time )
			{
				AllWaitTime++;
			}
		}

3、客户的入队

遍历窗口，如果发现有窗口为0 并且队列不为空，此时就应该考虑让客户进入新窗口进行处理了，但是要注意，如果此时队首客户的到达时间比time要大，说明该客户还没有到达银行，此时应该终止入队，继续time的自加，直到该客户到达了银行

同时在这个过程中，每当一个客户进入到窗口中，那么他的等待时间应该为 time - cust[front].arrive;然后使用 MaxWaitTime 保存最大等待时间即可

随后进行的便是 result[j] 的自加和客户入窗口操作

		for(int j = 0;j < k;j++)
		{
			if(window[j] == 0 && front != n)
			{
				if(cust[front].arrive > time)break; //说明客户还没有到达银行
				cust[front].wait = time - cust[front].arrive; 
				if(MaxWaitTime < cust[front].wait)MaxWaitTime = cust[front].wait;
				result[j]++;
				window[j] = cust[front++].process;
			}
		}

4、判断是否已经处理完成

上述过程处理完成后，接下来就是对是否处理完成的判断，设置一个变量t ，然后对window[ ]进行遍历累加，

码农公寓