1025.cpp

pku 1025 Department 北大ACM网站 模拟题

//pku 1025
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

inline string NumToStr(int n)
{
	string str;
	str=(char)(n/10)+'0';
	str+=(char)(n%10)+'0';
	return str;
}

struct TIME
{
	char hour;
	char minu;
	char sec;
	TIME(char _hour=0,char _minu=0,char _sec=0)
	{
		hour=_hour;minu=_minu;sec=_sec;
	}
	void set(char _hour,char _minu,char _sec)
	{
		hour=_hour;minu=_minu;sec=_sec;
	}
	void Add(int secAdd)
	{
		int minAdd=((int)sec+secAdd)/60;
		sec=((int)sec+secAdd)%60;
		int houAdd=((int)minu+minAdd)/60;
		minu=((int)minu+minAdd)%60;
		hour=((int)hour+houAdd);
	}
	bool operator <(const TIME& t) const
	{
		return hour<t.hour||hour==t.hour&&minu<t.minu||hour==t.hour&&minu==t.minu&&sec<t.sec;
	}
	bool operator ==(const TIME& t) const
	{
		return hour==t.hour&&minu==t.minu&&sec==t.sec;
	}
	string ToString()
	{//转化为字符串
		string str;
		str=NumToStr(hour%24);
		str+=":";
		str+=NumToStr(minu);
		str+=":";
		str+=NumToStr(sec);
		return str;
	}
	void FromString(string str)
	{
		int i=0;
		hour=(str.data()[i]-'0')*10+(str.data()[i+1]-'0');
		i+=3;
		minu=(str.data()[i]-'0')*10+(str.data()[i+1]-'0');
		i+=3;
		sec=(str.data()[i]-'0')*10+(str.data()[i+1]-'0');
	}
};
string GetRoomName(int floor,int roomId)
{
	string str;
	str=NumToStr(floor);
	str+=NumToStr(roomId);
	return str;
}
inline void GetRoomNum(int& floor,int& roomId,string str)
{
	floor=(str.data()[0]-'0')*10+(str.data()[1]-'0');
	roomId=(str.data()[2]-'0')*10+(str.data()[3]-'0');
}
//////////////////////////////////////////////////////////////////////////
//事件
struct Event
{
	int floor;
	TIME tmStart;//事件开始时间
	TIME tmEnd;
	virtual string Name()=0;
};
struct EvWaitInQ:public Event
{//在队列中等待
	int nRoomId;
	EvWaitInQ(TIME _tmStart,int _floor,int _nRoomId)
	{
		tmEnd=tmStart=_tmStart;
		floor=_floor;
		nRoomId=_nRoomId;
	}
	string Name()
	{
		string str=tmStart.ToString();
		str+=" ";
		str+=tmEnd.ToString();
		str+=" ";
		if(nRoomId==0)//电梯
			str+="Waiting in elevator queue";
		else
		{
			str+="Waiting in front of room ";
			str+=GetRoomName(floor,nRoomId);
		}
		return str;
	}
};
struct EvTransfer:public Event
{
	int nRoomIdFrom,nRoomIdTo;
	EvTransfer(TIME _tmStart,int _floor,int _nRoomIdFrom,int _nRoomIdTo)
	{//移动
		nRoomIdFrom=_nRoomIdFrom;
		nRoomIdTo=_nRoomIdTo;
		//////////////////////////////////////////////////////////////////////////
		tmEnd=tmStart=_tmStart;
		if (nRoomIdFrom==-1||nRoomIdTo==-1)//Entry||Exit
			tmEnd.Add(30);
		else tmEnd.Add(10);
		floor=_floor;
	}
	string Name()
	{
		string str=tmStart.ToString();
		str+=" ";
		str+=tmEnd.ToString();
		str+=" ";
		//////////////////////////////////////////////////////////////////////////
		if (nRoomIdFrom==-1||nRoomIdTo==-1)
		{//进入/离开
			if (nRoomIdFrom==-1)
				str+="Entry";
			else str+="Exit";
			return str;
		}
		//////////////////////////////////////////////////////////////////////////
		str+="Transfer from ";
		if(nRoomIdFrom==0)//电梯
			str+="elevator";
		else
			str+="room "+GetRoomName(floor,nRoomIdFrom);
		str+=" to ";
		if(nRoomIdTo==0)//电梯
			str+="elevator";
		else
			str+="room "+GetRoomName(floor,nRoomIdTo);
		return str;
	}
};
struct EvStay:public Event
{
	int nRoomId;
	EvStay(TIME _tmStart,int floorFrom,int floorTo,int _nRoomId)
	{//结束时间统一在外面设
		floor=floorFrom;
		tmEnd=tmStart=_tmStart;
		nRoomId=_nRoomId;
	}
	string Name()
	{
		string str=tmStart.ToString();
		str+=" ";
		str+=tmEnd.ToString();
		str+=" ";
		//////////////////////////////////////////////////////////////////////////
		str+="Stay in ";
		if (nRoomId==0)
			str+="elevator";
		else
			str+="room "+GetRoomName(floor,nRoomId);
		return str;
	}
};
//////////////////////////////////////////////////////////////////////////
struct Task
{
	int floor,roomId;//floor对于房间指的是其所在层，对于电梯指的是其预到达的层
	int nTmLen;//持续时间
};
//////////////////////////////////////////////////////////////////////////
//GOTOROOM:准备进入房间;GOTOQ:从QWait中出来，准备进入QRoom；COMPLETE:完成所有任务，已离开
enum AGSTAT{ENTRY,GOTOROOM,GOTOQ,COMPLETE};
struct Agent
{
	int index;//在vecAg中的下标
	AGSTAT stat;
	char ID;
	int curFloor;//当前所在楼层
	TIME tmCur;//当前待处理事件时间
	vector<Event*> vecEvent;//事件列表
	queue<Task> QTask;//任务列表,最后加一个退出任务，floor=1,roomId=-1,nTmLen=0
	//在Task列表中加入电梯任务，即对于层数发生变化的任务，中间加入电梯，其floor为下一任务的层数，时间为5×层数
	bool operator <(const Agent& ag) const
	{
		return ID<ag.ID;
	}
	bool Init()
	{//返回true说明成功初始化，否则说明已没有Agent
		if (!(cin>>ID)||ID=='.')
			return false;
		string str;
		cin>>str;
		tmCur.FromString(str);
		InitQTask();
		curFloor=1;
		stat=ENTRY;
		return true;
	}
	void InitQTask();
	//////////////////////////////////////////////////////////////////////////
	void CheckTask();
	void Entry();
	void GoToQ();
	void GoToRoom();
	void Transfer(Task& laskTask);
	void Print();
};
vector<Agent> vecAg;
struct AgIDLess
{
	bool operator()(const int& ag1,const int& ag2)
	{
		return vecAg[ag1].ID>vecAg[ag2].ID;
	}
};
struct AgTimeIDLess
{
	bool operator()(const int& ag1,const int& ag2)
	{
		return vecAg[ag2].tmCur<vecAg[ag1].tmCur||
			vecAg[ag1].tmCur==vecAg[ag2].tmCur&&vecAg[ag1].ID>vecAg[ag2].ID;
	}
};
struct AgFloorLess
{
	bool operator()(const int& ag1,const int& ag2)
	{
		return vecAg[ag1].curFloor>vecAg[ag2].curFloor;
	}
};
struct Room
{
	TIME tmCur;
	priority_queue<int,vector<int>,AgIDLess> QWait;
	int Pop()
	{//出等待队列时更新等待事件结束时间及Agent的当前时间
		int i=QWait.top();
		vecAg[i].tmCur=vecAg[i].vecEvent[vecAg[i].vecEvent.size()-1]->tmEnd=tmCur;
		QWait.pop();
		return i;
	}
};
//////////////////////////////////////////////////////////////////////////
Room room[11];//0为电梯，1～10为当前层的房间号
priority_queue<int,vector<int>,AgTimeIDLess> QAgWait;//正在等待的Agent
priority_queue<int,vector<int>,AgFloorLess> QAgOthflo;//已离开当前楼层的Agent
int curProcFloor;
//////////////////////////////////////////////////////////////////////////
void Agent::InitQTask()
{
	while (!QTask.empty())
		QTask.pop();
	char buffer[50]={0};
	Task lastTask;bool bFirst=true;
	while(scanf("%s",buffer)&&buffer[1]!=0)
	{
		Task task;
		GetRoomNum(task.floor,task.roomId,buffer);
		scanf("%d",&task.nTmLen);
		if (bFirst)
		{
			bFirst=false;
			if (task.floor!=1)
			{
				lastTask.floor=task.floor;lastTask.roomId=0;lastTask.nTmLen=abs(task.floor-1)*30;
				QTask.push(lastTask);
			}
		}
		else
		{
			if(lastTask.floor!=task.floor)
			{
				lastTask.nTmLen=abs(lastTask.floor-task.floor)*30;
				lastTask.floor=task.floor;lastTask.roomId=0;
				QTask.push(lastTask);
			}
		}
		QTask.push(task);
		lastTask=task;
	}
	if (lastTask.floor!=1)
	{
		lastTask.nTmLen=abs(lastTask.floor-1)*30;
		lastTask.floor=1;lastTask.roomId=0;
		QTask.push(lastTask);
	}
	lastTask.floor=1;lastTask.nTmLen=0;lastTask.roomId=-1;
	QTask.push(lastTask);
}
//一次处理流程是Agent从一个队列中出来，到另一个队列中去
void Agent::CheckTask()
{//调用此函数时，已经到达房间或电梯的旁边
	switch(stat)
	{
	case ENTRY:
		Entry();
		break;
	case GOTOROOM:
		GoToRoom();
		break;
	case GOTOQ:
		GoToQ();
		break;
	case COMPLETE:
		break;
	default:
		break;
	}
}
void Agent::Entry()
{
	stat=GOTOQ;
	vecEvent.push_back(new EvTransfer(tmCur,1,-1,-1));
	tmCur.Add(30);
	QAgWait.push(index);
}
void Agent::GoToQ()
{//stat==GOTOQ
	Task task=QTask.front();
	if(task.floor!=curProcFloor&&task.roomId!=0)
	{
		QAgOthflo.push(index);//将该Agent压入其他层待处理队列
		return;
	}
	stat=GOTOROOM;
	//////////////////////////////////////////////////////////////////////////
	if (task.roomId==0&&room[task.roomId].QWait.empty()&&
		((tmCur.sec%5)||tmCur<room[task.roomId].tmCur))
	{//对于电梯，保证5的倍数进入电梯,且Agent的当前时间<电梯的当前时间
		room[task.roomId].tmCur=tmCur;
		room[task.roomId].tmCur.Add(5-tmCur.sec%5);
		vecEvent.push_back(new EvWaitInQ(tmCur,task.floor,task.roomId));
		room[task.roomId].QWait.push(index);
	}
	else if (room[task.roomId].QWait.empty()&&!(tmCur<room[task.roomId].tmCur)||
		!room[task.roomId].QWait.empty()&&*this<vecAg[room[task.roomId].QWait.top()]&&tmCur==room[task.roomId].tmCur)//无等待过程
	{
		//在出QRoom时会更新Agent时间为Room时间
		//但此处应更新Room时间为Agent时间
		room[task.roomId].tmCur=tmCur;
		GoToRoom();
	}
	else
	{
		vecEvent.push_back(new EvWaitInQ(tmCur,task.floor,task.roomId));
		room[task.roomId].QWait.push(index);
	}
}
void Agent::GoToRoom()
{
	Task task=QTask.front();
	QTask.pop();
	vecEvent.push_back(new EvStay(tmCur,curFloor,task.floor,task.roomId));
	tmCur.Add(task.nTmLen);//更新Agent时间
	vecEvent[vecEvent.size()-1]->tmEnd=tmCur;//设置事件结束时间
	//更新房间时间
	if(task.roomId)
		room[task.roomId].tmCur.Add(task.nTmLen);
	else //电梯
		room[task.roomId].tmCur.Add(5);
	curFloor=task.floor;//更新所在层
	//////////////////////////////////////////////////////////////////////////
	Transfer(task);
}
void Agent::Transfer(Task& laskTask)
{
	Task task=QTask.front();
	vecEvent.push_back(new EvTransfer(tmCur,laskTask.floor,laskTask.roomId,task.roomId));
	if (task.roomId==-1)
	{//退出
		tmCur.Add(30);
		QTask.pop();
		stat=COMPLETE;
	}
	else
	{//压入QAgWait队列，等待处理
		tmCur.Add(10);
		stat=GOTOQ;
		QAgWait.push(index);
	}
}
void Agent::Print()
{
	printf("%c\n",ID);
	for (int i=0;i<vecEvent.size();i++)
	{
		string str=vecEvent[i]->Name();
		delete vecEvent[i];
		printf("%s\n",str.c_str());
	}
	printf("\n");
	vecEvent.clear();
}
//////////////////////////////////////////////////////////////////////////
int GetRoom()
{
	int index=-1;
	TIME tm;
	for (int i=0;i<11;i++)
	{
		if (room[i].QWait.empty())
			continue;
		if (index==-1)
		{
			tm=room[i].tmCur;
			index=i;
		}
		else
		{
			if (room[i].tmCur<tm)
			{
				tm=room[i].tmCur;
				index=i;
			}
		}
	}
	return index;
}
void PrintAll()
{
	for (int i=0;i<vecAg.size();i++)
		vecAg[i].Print();
}
void MainProc()
{
	curProcFloor=1;
	for(int i=0;i<vecAg.size();i++)
	{//初始化
		vecAg[i].CheckTask();
	}
	for(int i=0;i<11;i++)
		room[i].tmCur.set(0,0,0);
	while(1)
	{
		int nRoomIdx=GetRoom();
		if (nRoomIdx==-1&&QAgWait.empty())
		{//当前层均已处理完
			if (QAgOthflo.empty())
			{//结束
				PrintAll();
				return;
			}
			//更新当前处理层
			int i;
			do {
				i=QAgOthflo.top();
				QAgOthflo.pop();
				QAgWait.push(i);
			}while (!QAgOthflo.empty()&&vecAg[QAgOthflo.top()].curFloor==vecAg[i].curFloor);
			curProcFloor=vecAg[i].curFloor;
			for(int i=0;i<11;i++)
				room[i].tmCur.set(0,0,0);
		}
		else if (QAgWait.empty()||nRoomIdx!=-1&&room[nRoomIdx].tmCur<vecAg[QAgWait.top()].tmCur)
		{//处理房间等待队列中的Agent
			int index=room[nRoomIdx].Pop();
			vecAg[index].CheckTask();
		}
		else 
		{//处理QAgWait等待队列中的Agent,room[index].tmCur==vecAg[QAgWait.top()].tmCur时优先处理AgWait
			int index=QAgWait.top();
			QAgWait.pop();
			vecAg[index].CheckTask();
		}
	}
}

int main(int argc, char* argv[])
{
	Agent ag;
	while (ag.Init())
	{
		vecAg.clear();
		do
		{
			vecAg.push_back(ag);
		}while(ag.Init());
		sort(vecAg.begin(),vecAg.end());
		for(int i=0;i<vecAg.size();i++)
			vecAg[i].index=i;
		MainProc();
		break;
	}
	return 0;
}