PTA甲级考试真题练习17——1017 Queueing at Bank

题目

思路

跟1014有点像，但是有些许不一样，比如1014是客户同时到达而这个给了每个客户到达的时间，1014分了两个排队队列，而这里就只有窗口和一个大的排队队列

坑点

题目中说17：00之前到达的都会给予服务，而17:00后到达的就不服务也不算平均等待，这是和1014不同的地方，1014中如果客户17:00之前到达但是17:00之后才开始服务就不会服务，而此题只要是17:00到达的不管是排队多久都会处理

代码

#include <iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<list>
using namespace std;
#define nmax 100  //一个用作示例的小顺序表的最大长度

typedef struct Event
{
	int OccurTime;
	int Duration;
	int NType;  //0表示到达事件，1~n为窗口离开事件
}Event;


queue<Event> wait_queue;
list<Event> ev;
vector<bool> isFill;
Event en;
int waitTime = 0;
int num, window_n;

void InsertList(const Event& env)
{
	if (ev.empty())
	{
		ev.emplace_back(env);
		return;
	}
	for (auto iter = ev.begin(); iter != ev.end(); ++iter)
	{
		if (env.OccurTime >= iter->OccurTime)
		{
			ev.insert(iter, env);
			return;
		}
	}
	ev.emplace_back(env);
}

void OpenForDay()
{
	cin >> num >> window_n;
	//初始化窗口队列
	for (int i = 0; i < window_n; ++i)
	{
		isFill.push_back(false);
	}
	//初始化时间队列
	for (int i = 0; i < num; ++i)
	{
		int hour, minute, second;
		scanf_s("%d:%d:%d %d", &hour, &minute, &second, &en.Duration);
		en.NType = 0;
		en.OccurTime = hour * 3600 + minute * 60 + second;
		en.Duration *= 60;
		InsertList(en);
	}
}

void CustomerArrived()
{
	if (en.OccurTime < 28800)
	{
		waitTime += 28800 - en.OccurTime;
		en.OccurTime = 28800;
	}
	if (en.OccurTime >= 61200)
	{
		num--;
		return;
	}
	//判断窗口有没有空
	for (int i = 0; i <isFill.size(); ++i)
	{
		//如果有空位
		if (isFill[i] == false)
		{
			isFill[i] = true;
			Event depart;
			depart.NType = i + 1;
			depart.OccurTime = en.OccurTime + en.Duration;
			InsertList(depart);
			return;
		}
	}
	//窗口没空就进入等待队列
	wait_queue.push(en);
}
void CustomerDepatured()
{
	int i = en.NType - 1;
	isFill[i] = false;
	if (!wait_queue.empty())
	{
		if (en.OccurTime > 61200)
		{
			while (!wait_queue.empty())
			{
				Event depart = wait_queue.front();
				wait_queue.pop();
				waitTime += 61200 - depart.OccurTime;
			}
			return;
		}
		else
		{
			isFill[i] = true;
			Event depart = wait_queue.front();
			wait_queue.pop();
			waitTime += en.OccurTime - depart.OccurTime;
			depart.OccurTime = en.OccurTime + depart.Duration;
			depart.NType = en.NType;;
			InsertList(depart);
			return;
		}
	}
}
int main()
{
	OpenForDay();
	while (!ev.empty())
	{
		auto iter = ev.rbegin();
		en = *iter;
		ev.pop_back();
		if (en.NType == 0)
			CustomerArrived();
		else
			CustomerDepatured();
	}
	double aver_wait = (double)waitTime / 60 / num;
	printf("%.1lf", aver_wait);
}