[PAT-A 1017]Queueing at Bank

[PAT-A 1017]Queueing at Bank
题目大意:
N个客户,K个窗口,给出每个客户的到达时间和服务时长,如果所有窗口都被占用,那么客户排队等候,如果窗口有空闲,那么由队列的第一个客户前往接受服务。求客户的平均等待时常。
银行开放时间8:00-17:00,在8:00之前到达的需要等待,在17:00之后还未被服务的客户不计算在内。
超过1小时的服务时长会被压缩为1小时。

思路:
1.定义结构体存放每个顾客的到达时间与服务时间,在读入数据后对所有17:00:00之前到达的客户按照到达时间从前到后进行排序,形成一个客户队列。
2.以数组endTime[k]存放每一个窗口当前客户的服务结束时间,即到了这个时间这个窗口会空闲,客户就可以前往服务,,需要将最早空闲的窗口找出来,让队首的客户前往该窗口,在此过程中,同时更新对应窗口的endTime的值。
1)如果队首客户到达的时间比该最早空闲的窗口的时间要早晚,那么客户可以直接前往服务,等待时间为0,即只需要令该窗口的endTime值增加该客户的服务时常。
2)如果队首客户的到达时间比该最早空闲的窗口时间要早,说明客户需要等待两者时间差的时间,才能前往接受服务,前方服务时更新该窗口的endTime值。
3.可以将所有的时间换算为s处理。
4.如果窗口数比17:00:00之前到达的客户要多,那么直接输出0.0.

AC代码:

//PAT_A 1017
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int inf = 0x3fffffff;
const int k = 111;
struct Customer{
	int comeTime, serveTime;
};
vector<Customer> custom;
int convertTime(int h, int m, int s) {
	return h * 3600 + m * 60 + s;
}
bool cmp(Customer a, Customer b) {//按先来后到的顺序排序
	return a.comeTime < b.comeTime;
}
int main() {
	int c, w, totalTime = 0, endTime[k];//客户数 窗口数 总服务时间 每一个窗口当前服务客户的结束时间
	int stTime = convertTime(8, 0, 0), edTime = convertTime(17, 0, 0);
	(void)scanf("%d %d", &c, &w);
	for (int i = 0; i < w; i++) {
		endTime[i] = stTime;//窗口开始服务时间初始化为8:00
	}
	for (int i = 0; i < c; i++) {
		int hh, mm, ss, severTime;
		(void)scanf("%d:%d:%d %d", &hh, &mm, &ss, &severTime);
		int comeTime = convertTime(hh, mm, ss);
		if (comeTime > edTime)continue;
		Customer newCustomer;
		newCustomer.comeTime = comeTime;
		if (severTime >= 60)newCustomer.serveTime = 3600;
		else newCustomer.serveTime = severTime * 60;
		custom.push_back(newCustomer);
	}
	sort(custom.begin(), custom.end(), cmp);
	for (int i = 0; i < custom.size(); i++) {
		int index = -1, minEndTime = inf;
		for (int j = 0; j < w; j++) {//最早结束服务的窗口
			if (endTime[j] < minEndTime) {
				minEndTime = endTime[j];
				index = j;
			}
		}
		if (endTime[index] <= custom[i].comeTime) {//顾客在窗口空闲之后才来
			endTime[index] = custom[i].comeTime + custom[i].serveTime;
		}
		else {
			totalTime += endTime[index] - custom[i].comeTime;
			endTime[index] += custom[i].serveTime;
		}
	}
	if (custom.size() == 0)printf("0.0");
	else printf("%.1f", totalTime / 60.0 / custom.size());
	return 0;
}
上一篇:SQL(3)— WHERE 中运算符


下一篇:bargain