1014. Waiting in Line (30)

题目如下：

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• 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.
• 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.
• Customer[i] will take T[i] minutes to have his/her transaction processed.
• 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, customer₁ is served at window₁ while customer₂ is served at window₂. Customer₃ will wait in front of window₁ and customer₄ will wait in front of window₂. Customer₅ will wait behind the yellow line.

At 08:01, customer₁ is done and customer₅ enters the line in front of window₁ since that line seems shorter now. Customer₂ will leave at 08:02, customer₄ at 08:06, customer₃ at 08:07, and finally customer₅ at 08:10.

Input

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

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

考察模拟现实的问题，看起来十分复杂，其实只要把实际问题转化为数据结构模型，是十分简单和自然的。

       一个自然的思路是建立人、窗口、黄线后三个部分的结构体，其中人存放需要的服务时间、离开的时间；窗口和黄线都是队列，由于窗口有多个，采用vector来容纳这些窗口，人也同样通过vector容纳，为了让人的编号从1开始，在向vector中压入人的信息时先压入一个无用元素。 

       对于人结构体的成员，需要额外存储一个服务时间，其中一个服务时间在程序运行过程中不断减少，当为0时离队，而那个额外的用于判断服务是否在17:00之前开始（这道题目有个问题需要注意的是，如果服务在17:00之前开始，即使超时，仍然是允许的，而不是输出Sorry），判断方法是用离开时间减去这个时间，得到开始服务的时间，看是否在17:00之前，在17:00之前应该正常输出（有三个case涉及到这个问题）。

       设定一个全局变量clk_cnt用来记录时间的流逝。

模拟的过程应该按照下面的规则进行：

①将编号为1到N*M的人依次放入窗口队列0到N-1，从左到右，到了N-1之后再返回1放入。

②将编号为N*M+1到K的人依次插入黄线后队列。

③如果窗口队列为空，则说明所有人都已经服务结束，结束模拟。否则从所有窗口队列头部选出服务时间最短的记录在min_t中，再遍历所有窗口队列，对所有非空的队列，头部的服务时间减去min_t，如果为0则说明服务结束，出队。

④如果黄线后队列不空，并且有空闲的窗口队列，则每次从空闲窗口队列中找出人数最少的（从编号小的开始判断，可以满足多个窗口成立编号小的优先的条件），从黄线后队列中出队一个元素插入这个窗口，直到不满足本条开头所述的条件。

⑤重复3至4，直到不满足3开头所述条件，结束模拟。

⑥对要查询的数据进行输出，依据为离开的时刻和服务的总时长。

代码如下：

#include<iostream>
#include<memory.h>
#include<vector>
using namespace std;

int N, M, K, Q;
int clk_cnt = 0;

#define INF 99999999

typedef struct Person_s *Person;
struct Person_s{
	int time;
	int serve_time;
	int leave;
	int num;
	Person_s(int _t,int _l,int _n) :time(_t),leave(_l),num(_n){}

};

typedef struct Window_Queue_s *WQueue;
struct Window_Queue_s{
	int capacity;
	int front;
	int rear;
	Person data[1002];

	Window_Queue_s(int _cap) :capacity(_cap) {
		front = rear = 1;
	}
};

typedef struct Wait_Queue_s *YQueue;
struct Wait_Queue_s{
	int front;
	int rear;
	Person data[1002];

	Wait_Queue_s(){
		front = rear = 1;
	}
};

void EnqueueWindow(WQueue q, Person p){
	q->data[q->rear++] = p;

}

Person DequeueWindow(WQueue q){
	if (q->front == q->rear) { cout << "underflow" << endl; exit(0); }
	
	return q->data[q->front++];
}

bool IsWindowFull(WQueue q){
	return (q->rear - q->front) == q->capacity;
}

bool IsWindowEmpty(WQueue q){
	return q->rear == q->front;
}

int WindowLength(WQueue q){
	return q->rear - q->front;
}

Person WindowQueueTop(WQueue q){
	if (q->front == q->rear) { cout << "underflow" << endl; exit(0); }
	return q->data[q->front];
}

void EnqueueYellow(YQueue q, Person p){
	q->data[q->rear++] = p;
}

Person DequeueYellow(YQueue q){
	if (q->front == q->rear) { cout << "underflow" << endl; exit(0); }
	return q->data[q->front++];
}

Person YellowQueueTop(YQueue q){
	if (q->front == q->rear) { cout << "underflow" << endl; exit(0); }
	return q->data[q->front];
}

bool IsYellowEmpty(YQueue q){
	return q->rear == q->front;
}


void showPerson(Person p){
	printf("%02d: time = %d leave = %d
",p->num, p->time, p->leave);
}

vector<Window_Queue_s> windows;

bool checkWindow(){

	for (int i = 0; i < windows.size(); i++){
		if (!IsWindowEmpty(&windows[i])){
			return true;
		}
	}

	return false;

}

bool hasVacuWindow(){

	for (int i = 0; i < windows.size(); i++){
		if (!IsWindowFull(&windows[i])){
			return true;
		}
	}

	return false;
}

int main(){

	cin >> N >> M >> K >> Q;

	vector<Person_s> persons;

	persons.push_back(Person_s(-1, -1, -1));

	int timeCost = 0;

	for (int i = 0; i < K; i++){
		scanf("%d", &timeCost);
		persons.push_back(Person_s(timeCost, 0, i+1));
		persons[i + 1].serve_time = timeCost;
	}

	for (int i = 0; i < N; i++){
		windows.push_back(Window_Queue_s(M));
	}

	int window_num = 0;
	int cnt = N * M > K ? K : N * M;

	for (int i = 0; i < cnt; i++){
		window_num = i % N;
		EnqueueWindow(&windows[window_num], &persons[i + 1]);
	}

	Wait_Queue_s wait_q = Wait_Queue_s();

	for (int i = N*M + 1; i <= K; i++){
		EnqueueYellow(&wait_q, &persons[i]);
	}

	int min_t = 0, min_num = 0;
	Person topPerson = NULL;
	int min_window_num = -1;
	int min_window_length = INF;
	WQueue window = NULL;

	while (checkWindow()){

		min_t = INF;
		for (int i = 0; i < windows.size(); i++){
			if (IsWindowEmpty(&windows[i])) continue;
			topPerson = WindowQueueTop(&windows[i]);
			if (min_t > topPerson->time){
				min_t = topPerson->time;
			}
		}
		clk_cnt += min_t;
		for (int i = 0; i < windows.size(); i++){
			if (IsWindowEmpty(&windows[i])) continue;
			topPerson = WindowQueueTop(&windows[i]);
			topPerson->time -= min_t;
			if (topPerson->time == 0){
				topPerson->leave = clk_cnt;
				DequeueWindow(&windows[i]);
			}
		}

		while(!IsYellowEmpty(&wait_q) && hasVacuWindow()){
			min_window_length = INF;
			min_window_num = -1;
			for (int i = 0; i < windows.size(); i++){
				window = &windows[i];
				if (!IsWindowEmpty(window))
				{
					if (min_window_length > WindowLength(window)){
						min_window_length = WindowLength(window);
						min_window_num = i;
					}
				}
			}
			topPerson = DequeueYellow(&wait_q);
			EnqueueWindow(&windows[min_window_num], topPerson);
		}

	}
	int hour = 0, minute = 0;
	int query = 0;
	for (int i = 0; i < Q; i++){
		cin >> query;
		topPerson = &persons[query];
		if (topPerson->leave == 0 || (topPerson->leave - topPerson->serve_time) >= 540){
			printf("Sorry
");
		}
		else{
			hour = 8 + topPerson->leave / 60;
			minute = topPerson->leave % 60;
			printf("%02d:%02d
", hour, minute);
		}
	}

	return 0;
}