PAT 1017. Queueing at Bank (25)

PATEST链接地址：http://www.patest.cn/contests/pat-a-practise/1017
Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.
Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.
此题主要是要注意几个点：

• 8点之前到的顾客要等8点开门
• 17点之后到的顾客就不能进入了（不算入平均时间），但是17点之前到的，可以拖到17点之后完成

有两种思路，一种是像http://www.cnblogs.com/Rafy/archive/2012/03/20/2408419.html一样按照一秒一秒tick，还有一种是我的思路，把客户按照时间顺序排序，然后一个个“喂”给窗口。
窗口只需记录当前任务能完成的时间点T1。客户进入时间为T0。喂给窗口时就两个状况：

1. 如果窗口现在有工作，那等待的时间就是T1-T0；
2. 如果窗口现在空置（T1<T0），那么等待时间为0；

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
struct Customer
{
	int comeInTime; //到达时间（秒）
	int processingTime; //处理时间（秒）
};
int* nextAvailableTime; //窗口的下个可用时间点，用秒记录
Customer* customers;
int N, K, N_valid;
int compareCustomers(const void* c1, const void* c2)
{
	//时辰早的排在前面
	Customer* C1 = (Customer*)c1;
	Customer* C2 = (Customer*)c2;
	return C1->comeInTime - C2->comeInTime;
}
int getNextAvailable(Customer c)
{
	//找到下个可用窗口，返回等待时间
	int minTime = 100000; //这个值不能是17:00:00(61200),至少得是86400，因为有可能17点之前来的顾客会等到17点之后...;
	int minIndex = -1;
	for (int i = 0; i < K; i++)
	{
		if (nextAvailableTime[i] < minTime)
		{
			minTime = nextAvailableTime[i];
			minIndex = i;
		}
	}
	if (nextAvailableTime[minIndex] < c.comeInTime)
	{
		//之前就已经空窗；
		nextAvailableTime[minIndex] = c.comeInTime + c.processingTime;
		return 0;
	}
	else
	{
		int waitTime = nextAvailableTime[minIndex] - c.comeInTime;
		nextAvailableTime[minIndex] += c.processingTime;
		return waitTime;
	}
}
int main()
{
	scanf("%d %d", &N, &K);
	customers = new Customer[N];
	nextAvailableTime = new int[K];
	for (int i = 0; i < K; i++)
		nextAvailableTime[i] = 8 * 3600; // 8:00:00
	N_valid = N;
	for (int i = 0; i < N_valid; i++)
	{
		int hh, mm, ss, procTime;
		scanf("%d:%d:%d %d", &hh, &mm, &ss, &procTime);
		if (hh >= 17 && mm >= 0 && ss > 0)
		{
			N_valid--;
			i--;
			continue;
		}
		else
		{
			customers[i].comeInTime = hh * 3600 + mm * 60 + ss;
			if (procTime > 60)
				procTime = 60;
			customers[i].processingTime = procTime * 60;
		}
	}
	//对有效顾客排序
	qsort(customers, N_valid, sizeof(Customer), compareCustomers);
	int waitTimeSum = 0; //(秒)
	for (int i = 0; i < N_valid; i++)
	{
		waitTimeSum += getNextAvailable(customers[i]);
	}
	float waitTimeAvg = waitTimeSum / 60.0 / (float)N_valid;
	printf("%.1f", waitTimeAvg);
	return 0;
}