欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习26——1026 Table Tennis

程序员文章站 2022-06-07 13:06:35
...

题目

PTA甲级考试真题练习26——1026 Table Tennis

生词生字

  1. The waiting time must be rounded up to an integer minute(s)
    等待时间必须四舍五入成一个整数

思路

细节贼多的模拟题

坑点

  1. 测试点3:题目给的到达的人符合8点到21点,让我们误以为不用检测刚刚到达的人是否在21点之前到达,其实如果21点整到达的话也是不能服务的,要注意!!
  2. VIP顾客会先选择空闲VIP桌子中序号最小的桌子,如果没有空闲VIP桌子再选择序号最小的空闲桌子,所以要注意两个地方
    (1)当处理到达事件的时候,如果是VIP顾客要选择空闲VIP桌子中序号最小的桌子
    (2)当同时有离开事件发生的时候应该先处理VIP的桌子和序号小的桌子,这样处理后VIP顾客就能去VIP桌子了
  3. 当21点后还有等待顾客的话,只能说再见了
#include <iostream>
#include <string>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<sstream>
#include<string.h>
#include<math.h>
using namespace std;
#define nmax 105
#define inf 999999

int mark[nmax]; //窗口标记数组,0为普通窗口,1为vip窗口
typedef struct Event
{
	int OccurTime;
	int NType;  //时间发生顺序,0表示到达事件,1~n表示离开哪个桌子
	int Duration;   //打的时间
	int isVip;      //普通顾客为0,VIp为1
	bool operator < (const Event& a) const
	{
		if (OccurTime != a.OccurTime)
			return OccurTime < a.OccurTime;
		else
			if (NType == 0 || a.NType == 0)
				return NType < a.NType;
			else if (mark[NType] == 1 && mark[a.NType]==0)
			{
				if (NType < a.NType)
					return NType < a.NType;
				else
					return NType > a.NType;
			}
			else if (mark[a.NType] == 1 && mark[NType]==0)
			{
				if (NType < a.NType)
					return NType > a.NType;
				else
					return NType < a.NType;
			}
			else
				return NType > a.NType;
	}
}Event;
typedef struct userInfo
{
	int arrive_time;
	int serve_time;
	bool operator < (const userInfo& a) const
	{
		return serve_time < a.serve_time;
	}
}userInfo;
set<Event> ev;
Event en;
set<userInfo> infoset;
queue<Event> wait;
int n;  //来人数
int wn; // 窗口数
int vipwn; //VIP窗口数
int tables[nmax]; //窗口,0为空闲,1为占有
int countT[nmax];  //计数数组

void InitEvent()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int hour, minute, second,dur;
		scanf_s("%d:%d:%d %d %d", &hour, &minute, &second,&dur,&en.isVip);
		en.Duration = dur*60;
		en.OccurTime = hour * 3600 + minute * 60 + second;
		en.NType = 0;
		ev.insert(en);
	}
	memset(mark, 0, sizeof(mark));
	memset(tables, 0, sizeof(tables));
	memset(countT, 0, sizeof(countT));
	cin >> wn >> vipwn;
	for (int i = 0; i < vipwn; ++i)
	{
		int index;
		cin >> index;
		mark[index] = 1;
	}
}
void ArrivedEvent()
{
	int index = -1;
	//如果是VIP
	if (en.isVip)
	{
		bool havVIP = false;
		for (int i = 1; i <= wn; ++i)
		{
			if (tables[i] == 0 && mark[i] == 1)
			{
				index = i;
				havVIP = true;
				break;
			}
		}
		if (!havVIP)
		{
			for (int i = 1; i <= wn; ++i)
			{
				if (tables[i] == 0)
				{
					index = i;
					break;
				}
			}
		}
	}
	else
	{
		for (int i = 1; i <= wn; ++i)
		{
			if (tables[i] == 0)
			{
				index = i;
				break;
			}
		}
	}
	//查找剩余位置
	if(index!=-1)
	{
		//窗口被占用
		tables[index] = 1;
		//添加离开事件
		Event de;
		de.OccurTime = en.OccurTime + en.Duration;
		de.NType = index;
		de.isVip = en.isVip;
		if (en.Duration > 7200)
			de.OccurTime = en.OccurTime + 7200;
		else
			de.OccurTime = en.OccurTime + en.Duration;
		ev.insert(de);
		//添加用户记录
		userInfo info;
		info.arrive_time = info.serve_time = en.OccurTime;
		infoset.insert(info);
		//计数
		countT[index]++;
		return;
	}
	//加入等待队列
	wait.push(en);
}
void DepartureEvent()
{
	//第几个球桌的离开事件
	int index = en.NType;
	//处理离开事件
	tables[index] = 0;
	//如果等待队列不为空,则加入新的玩家
	if (!wait.empty())
	{
		//如果时间超过了
		if (en.OccurTime >= 75600)
		{
			//清空队列
			while (!wait.empty())
			{
				wait.pop();
			}
			return;
		}
		Event de;
		//如果是普通球桌,直接加入一个
		if (mark[index] == 0)
		{
			de = wait.front();
			wait.pop();
		}
		else
		{
			bool havVIP = false;
			//查看等待队列中是否有VIP顾客
			queue<Event> tmp;
			while (!wait.empty())
			{
				Event e = wait.front();
				wait.pop();
				if (e.isVip)
				{
					havVIP = true;
					de = e;
					break;
				}
				tmp.push(e);
			}
			while (!wait.empty())
			{
				Event e = wait.front();
				wait.pop();
				tmp.push(e);
			}
			wait.swap(tmp);
			if (!havVIP)
			{
				de = wait.front();
				wait.pop();
			}
		}
		//添加用户记录
		userInfo info;
		info.arrive_time = de.OccurTime;
		info.serve_time = en.OccurTime;
		infoset.insert(info);
		//构造离开事件
		if (de.Duration > 7200)
			de.OccurTime = en.OccurTime + 7200;
		else
			de.OccurTime = en.OccurTime + de.Duration;
		de.NType = index;
		ev.insert(de);
		//计数
		countT[index]++;
		//窗口被占用
		tables[index] = 1;
	}
}
int main()
{
	InitEvent();
	while (!ev.empty())
	{
		auto p = ev.begin();
		en = *p;
		ev.erase(p);
		if (en.NType == 0)
			ArrivedEvent();
		else
			DepartureEvent();
	} 
	//输出
	int hour1,hour2,minute1,minute2,second1,second2;
	for (auto& p : infoset)
	{
		hour1 = p.arrive_time / 3600;
		hour2 = p.serve_time / 3600;
		minute1 = p.arrive_time % 3600 / 60;
		minute2 = p.serve_time % 3600 / 60;
		second1 = p.arrive_time % 3600 % 60;
		second2 = p.serve_time % 3600 % 60;
		int wait_time = round((double)(p.serve_time - p.arrive_time) / 60);
		printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", hour1, minute1, second1, hour2, minute2, second2, wait_time);
	}
	cout << countT[1];
	for (int i = 2; i <= wn; ++i)
	{
		cout << " " << countT[i];
	}
	return 0;
}