1014.Waiting in Line

2017-11-10

英文描述

Waiting in Line (30)
Suppose a bank has N windows open for service. There is a yellow line in front of the windows which divides the waiting area into two parts. The rules for the customers to wait in line are:
1 The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
2 Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
3 Customer[i] will take T[i] minutes to have his/her transaction processed.
4 The first N customers are assumed to be served at 8:00am.
Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.
For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.
At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).
The next line contains K positive integers, which are the processing time of the K customers.
The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.
Output Specification:
For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output “Sorry” instead.
Sample Input:
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output:
08:07
08:06
08:10
17:00
Sorry

中文描述

通道等待
假设一个银行有N个服务窗口。窗口前的一条黄通道将等待区域分成两个部分。顾客的等待规则如下：
1 在每个窗口前黄色通道里面的空间足够容纳这个通道上的M个顾客。因此当N条通道占满了人的时候，NM + 1的那个顾客将会站在黄线后的区域等待。
2 当每个顾客在黄色通道后等待时，他们将会去选择最短的通道进入。如果有2条或多条通道具有相同的长度是，总是选择窗口号最小的通道。
3 顾客i需要t（i）分钟去办理他的业务。
4 银行早上8点开始上班。
5 现在给出每位顾客需要办理业务的时间，你要求出每位顾客办完他的业务时的时间。
举一个例子，假设这个银行有2个窗口，每个窗口可以容纳2个顾客在黄线里面等待着。这里有5个顾客办理业务的时间是1，2，6，4和3分钟。在早上8点，顾客1在窗口1办理业务，顾客2在窗口2办理业务，顾客3在窗口1前等待，顾客4在窗口2等待。顾客5在黄线外等。
在08：01分，顾客1办理完业务，并且顾客5就去窗口1千等待了，窗口1那个通道里的人最少。顾客2在08：02办理完业务，顾客4在08：06办理完业务，顾客3在08：07办理完业务，顾客5在08：10办理完业务。
输入规格：
每个文件包含一个测试用例。每个用例的第一行包含4个正整数：N（<= 20，窗口数），M（<= 10，窗口容量数），K（<= 1000，顾客数量），Q（<= 1000,需要查询这些顾客几点办理完业务）
下一行包含K个正整数，每个整数代表每个顾客需要办理业务的时间。
最后一行包含Q个正整数，是我们要求得这些顾客啥时候办理完业务。每个顾客被标记为1到N。
输出规格：
对于要查询的Q个用户，在一行内打印他们办理完业务时候的时间，格式是：小时：分钟，小时从08到17，分钟从00到59。注意，银行为客户提供服务的时间在17:00点之前，如果17:00之后还有客户需要我们服务，我们只能对他说“Sorry”
样例输入:
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
样例输出:
08:07
08:06
08:10
17:00

分析与解题

总算把这题读明白了，花了快20分钟。题意是否忽略了排队时间。假如早8点大家全都到了，有20个窗口，每个窗口容纳10人，那么前200个人是不是1秒就排好队了，其他800人在黄线外等着，等着去选择队伍最短的。还是只有10个人去排队，剩下的990个人在哪等着，去动态的选择队伍最短的。按道理讲显示中应该是我理解的那样，但从给的那个例子以及题目中要求好像不是这样的，也就是队伍有空你就进去。只有在黄线外的那些顾客采取动态选择队伍最短的进去。
此刻代码已经写了出来，过了2个点，得了16分，画了快两天的时间。昨天看了别人的代码和思路，大致跟我的是一样的。所以我想在大体思路上是没有什么问题了，剩下的应该就是细节的处理问题了。我在这里通过文字把思路整体撸一遍，通过10个队列来模拟排队方式，初始化的时候，将NM个人，放入队列中，第一个人在1队列1号位置，第二个人在2队列1号位置，依次类推。这一点我是使用了队号和位置号来确定是第几个人的，假如是i队列和m位置号，那也就是第（i – 1）* n + j个人所在位置。我看了其他人的代码有通过直接去余的方法来写，觉得是蛮简单的。第i个人就在第i % N的位置上，次数他并没有去考虑第几个队列和第几个位置，因为i是一直在增加的，所以这样去初始化队列是蛮方便的。初始化时要考虑一件事情，k（所有顾客）是否小于nm，所以在初始化的时候要进行判断，我使用的方法是在入队处去统计人数，当k是小于nm时候，如果统计的人数= nm时候就会自动结束的。我刚才去测试了边界情况，假使所有的值都是大于或者等于1的。之后就开始判断哪个队列的队头顾客先把业务办理完毕，当队头顾客业务办理完毕后，将此顾客对应的是第几号以及他所花费的时间累加其起来，算是他的结束时间。这一点在实现的时候颇麻烦的，啰里啰嗦的，可能是我没有设计好。我在这里把我的思路叙述一遍，我的队列里标记了顾客是第几个顾客以及他办理业务所花费的时间，字段名称是c和time，当时也没有想到较好的英文，c就是count的意思，计数的意思。这个队列设计的也是颇啰嗦，感觉就是没有设计感，是想到哪就搞到哪，我一直在纠结，出队与入队的操作，以及返回值的问题，我是在想返回结果体也就是element还是time字段，如果是element的话那么和它的出队参数将不一致，后来也没有想这个问题，就放到那了。当初始化完成后，我就开始找队头用时最少的顾客，我找的一定是一个对号最小且用时最少的顾客，之后我就返回这个顾客所在的队列以及这个顾客是第几个顾客，我是第几个顾客，我存储在了c中。整体循环我使用的是for i = 1 to k，也就是对这k个用户要进行一次出队和入队操作，之后分别统计他们的结束时间。之后有一点要谈的是，也就是银行的服务时间，银行在8：00到17：00之间接受服务请求，也就是当你17：00到的时候，哪怕你的服务时间是10个小时那，银行也会对你进行服务，但是当超过了17：00点，你就不能去申请服务了，对于这样的顾客，我们应该对他说sorry，明天再来吧。我在处理这一点的时候，是为每个队列添加了一个计时器，计时器的初值为0。现在又详细考虑了这件事情，感觉不行了，漏洞是在太多了。在思路上有一个大的点没有考虑到，需要改进一下思路。
昨天又去把代码改进了一番，整体的思路是所有顾客都要入队，当然所有顾客也都要出队，后来又思索了很多，最后剩下一个点没过，报的错误是段错误，昨天晚上也没有很好的想明白这个事情。今天早上起来，我觉得去读一读ZJU的代码，看看两者的思路中的差异到底在哪。因为ZJU的代码是cpp写的，所以会记录一番关于cpp的相关知识。刚才去看了ZJU的代码，思路清晰，代码也简洁，整体的思路跟我的是一样的，只不过我的实现看起来复杂太多了。
我决定还是放弃了，按照ZJU的思路去写一遍吧。说不定能发现自己的错误到底在哪。调试到要抓狂的阶段了，真的是找不出来是哪里错了。按照ZJU的方法写了一遍，又是一堆的错误。pass吧，这道题。

C语言实现

#include<stdio.h>
typedef struct
{
	int time; 
	int c;
}elem;
typedef struct
{
	elem qlen[30];
	int rear;
	int front;
	int length;
}queue;
queue win[30];
int info[2001];
int query[2001];
int end[2001];
int accumulate[30] = {0};
int n, m, k, q;
void initqueue()
{
	int i = 1;
	while(i <=  n)
	{
		accumulate[i] = 0;
		win[i].front = win[i].rear = 0;
		win[i].length = 0;
		i++;
	}
}
void enqueue(int i, elem node)
{
	if(win[i].length < m)
	{
		win[i].qlen[win[i].rear] = node;
		win[i].rear = (win[i].rear + 1) % m;
		win[i].length++;
	}
}
elem show(int i)
{
	return win[i].qlen[win[i].front];
}
void dequeue(int i)
{
	if(win[i].length > 0)
	{
		win[i].front = (win[i].front + 1) % m;
		win[i].length--;
	}
	
}
void input()
{
	scanf("%d%d%d%d", &n, &m, &k, &q);	
	int i = 1;
	while(i <= k)
	{
		scanf("%d", &info[i]);
		i++;
	}
	i = 1;
	while(i <= q)
	{
		scanf("%d", &query[i]);
		i++;
	}
}
elem min(int *num)
{
	elem m;
	m.time = 9999999;
	m.c = -1;
	int i = 1;
	while(i <=  n)
	{
		//统计队列不为空的最小值
		if(win[i].length > 0)
		{	
			if(m.time > show(i).time)
			{
				m = show(i);
				*num = i;
			}
		}
		i++;
	}
	return m;
}
void calc()
{
	int en = 0, de = 0;
	int i = 1;
	int count = 1;
	while(i <= m)
	{
		int j = 1;
		while(j <= n)
		{
			elem tmp;
			tmp.c = (i - 1) * n + j;
			tmp.time = info[(i - 1) * n + j];
			if(count <= k)
			{
				en++;
				enqueue(j, tmp);	
				count++;
			}
			j++;
		}
		i++;
	}

	int num; //窗口号
	elem tmp = min(&num); 
	while(tmp.c != -1)
	{
		tmp = min(&num); 

		if(accumulate[num] >= 540)
			end[tmp.c] = -1;
		else
		{
			end[tmp.c] = tmp.time + accumulate[num];
			accumulate[num] = end[tmp.c];
		}
		dequeue(num);
		de++;
		if(count <= k)
		{
			elem enq;
			enq.time = info[count];
			enq.c = count;
			en++;
			enqueue(num, enq);
			count++;
		}
	}
}
void formate()
{
	int i = 1;
	while(i <= q)
	{
		if(end[query[i]] != -1)
		{
			int hour,minutes;
			hour = 8 + end[query[i]] / 60;
			minutes = end[query[i]] % 60; 
			printf("%02d:%02d\n", hour, minutes);
		}
		else
			puts("Sorry");
		i++;
	}
}
int main()
{
	input();
	initqueue();
	calc();
	formate();
	return 0;
}

测试链接

click me