http://poj.org/problem?id=1025
#include <iostream>
class Room {
public:
int fNo , rNo; // rNo表示房间号，fNo表楼层号，其中fNo-2表楼外。rNo=-1表示电梯
char * toString()
{ // 此函数线程不安全，不过用在此题没问题。千万不能在printf()这类函数内两次调用此函数。
static char str_room[5];
sprintf(str_room,"%02d%02d",fNo,rNo);
return str_room;
}
Room& operator = ( const Room& room ) { fNo=room.fNo; rNo=room.rNo; return *this; }
};
class Time {
public:
char tstr[9]; // Time类自带了用于转换的 char[]。
int h , m , s ;
Time() { h=m=s=0; }
Time(int hh,int mm,int ss) { h=hh; m=mm; s=ss; }
void setTime(char * str)
{
h = (str[0]-'0')*10 + (str[1]-'0') ;
m = (str[3]-'0')*10 + (str[4]-'0') ;
s = (str[6]-'0')*10 + (str[7]-'0') ;
}
char* toString() { sprintf(tstr,"%02d:%02d:%02d",h,m,s); return tstr; }
bool operator == (const Time& t){ return ( h==t.h && m==t.m && s==t.s ); }
Time& operator = (const Time& t){ h=t.h; m=t.m; s=t.s; return *this; }
bool operator < (const Time& t)
{
if(h!=t.h) return h<t.h;
if(m!=t.m) return m<t.m;
if(s!=t.s) return s<t.s;
return false;
}
Time& add(int n)
{
int temp;
if( n>=3600 )
{ temp = n/3600; h += temp; n -= temp*3600; }
if( n>=60 )
{
temp = n/60 ; m += temp; n -= temp*60 ;
if(m>=60) { m-=60; ++h; }
}
if( n<60 ) s += n ;
if( s>=60) { s-=60; ++m; }
return *this;
}
};
class Agent {
public:
char code;
Time startWait , nextTime ;
Room roomList[100]; // 最多访问 100 个房间
int lastTime[100] , totalRoom;
char actionList[100][60]; // 假设最多有100个action
int actNum , nextRoom , waitFlag;
Room pos ;
Agent* next;
Agent(char c,char* str)
{
code=c;
waitFlag = actNum = nextRoom = 0;
next=NULL;
nextTime.setTime(str);
pos.fNo=-2;
}
void doAct(); // 此函负责执行一个步骤
void moveTo(Room room); // 负责Agent的移动和访问room。包括乘电梯操作。
};
class AgentList {
public:
Agent* head ;
AgentList() { head=NULL; }
void add(Agent* ag)
{
Agent *par , *cur;
par = cur = head;
while( cur!=NULL && cur->code < ag->code )
{ par=cur; cur=cur->next; }
if(cur==head){ head=ag; ag->next=cur; return; }
par->next = ag;
ag->next = cur ;
}
void del(Agent *ag) // 只是取下节点，并未删除，这里会内存泄露！不过不想管了。
{
if(ag==head) { head=head->next; ag->next=NULL; return; }
Agent *par , *cur;
par = cur = head;
while( cur!=NULL && cur!=ag ) { par=cur; cur=cur->next; }
par->next = ag->next ;
ag->next = NULL;
}
};
/* ------------------------- 数据结构定义完毕 ----------------------------------- */
/***************************************************************************************/
Time roomTable[10][10] , elevator[10] , nowTime;
AgentList aglist , result ;
void Agent::moveTo( Room room ) // 此函数用于单步执行，包括访问房间和电梯两大块
{
//------------------------------ 以下是进电梯相关操作 ----------------------
if( pos.rNo!=-1 && room.rNo==-1 )
{
waitFlag = 0;
nextTime.add(10) ;
sprintf(actionList[actNum++],
"%s %s Transfer from room %s to elevatorn",
nowTime.toString(),nextTime.toString(),pos.toString() );
pos.rNo = -1; // 进入电梯或电梯等待队列
return ;
}
if( room.rNo==-1 ) // 如果需要进电梯
{
if( nowTime.s%5!=0 ) { // 时间不是 5s 倍数，则等待。
startWait = nowTime;
waitFlag=1; // 等待标识 waitFlag=1
nextTime.add( 5 - nextTime.s%5 );
sprintf(actionList[actNum++],
"%s %s Waiting in elevator queuen", startWait.toString(), nextTime.toString() );
pos.rNo = -1;
return;
}
else
{
if( nowTime < elevator[pos.fNo] ) // 如果优先级不高（电梯已有人），等待。
{
if( waitFlag==0 ){ startWait = nowTime; waitFlag=1; }
else --actNum;
nextTime.add( 5 );
sprintf(actionList[actNum++],
"%s %s Waiting in elevator queuen",startWait.toString(), nextTime.toString() );
pos.rNo = -1;
return;
}
else
{ // 乘电梯中
int et = (room.fNo-pos.fNo)*30 ;
et = ( et<0?(-et):et ) ;
nextTime.add( et );
sprintf(actionList[actNum++], "%s %s Stay in elevatorn", nowTime.toString() , nextTime.toString() );
elevator[pos.fNo] = nowTime.add( 5 ); // 电梯时间加 5
pos.fNo = room.fNo; // 楼层更新
waitFlag = 0 ;
return;
}
}
}
//----------------------- 以下是 出电梯 ---------------
if( pos.rNo==-1 && room.rNo!=-1 )
{
waitFlag = 0;
nextTime.add(10);
sprintf(actionList[actNum++],
"%s %s Transfer from elevator to room %sn",
nowTime.toString() , nextTime.toString() , room.toString());
pos.rNo = room.rNo ;
return ;
}
//----------------------- 以下是 同层房间访问 相关操作 -----------------------------
if( pos.rNo!=room.rNo )
{ // 不同房间，则花 10s 换房间
waitFlag = 0;
nextTime.add(10);
char temp[5];
strcpy(temp,room.toString());
sprintf(actionList[actNum++],
"%s %s Transfer from room %s to room %sn",
nowTime.toString(), nextTime.toString(), pos.toString(), temp );
pos.rNo = room.rNo ;
return ;
}
if( nowTime < roomTable[room.fNo][room.rNo] ) // 进入等待队列
{
nextTime = roomTable[room.fNo][room.rNo] ;
if( waitFlag==0 ) { startWait=nowTime; waitFlag=1; }
else --actNum;
sprintf(actionList[actNum++],
"%s %s Waiting in front of room %sn",
startWait.toString(), nextTime.toString(), room.toString() );
pos.rNo = room.rNo;
return ;
}
waitFlag = 0; // 等待标识 清除
nextTime.add( lastTime[nextRoom++] ); // 进入房间,
roomTable[room.fNo][room.rNo] = nextTime; // 更新房间信息
sprintf(actionList[actNum++],
"%s %s Stay in room %sn",
nowTime.toString(),nextTime.toString(),room.toString() );
pos.rNo = room.rNo;
return;
//-------------------------------------------------------
}
void Agent::doAct() // 执行函数，只执行一步（下面分为 进楼，访问，出楼 三种情况考虑 ）
{
Room roomTo;
//----------------- 以下处理出楼 -----------------------
if( nextRoom==totalRoom )
{
if( pos.fNo==1 )
{
nextTime.add(30);
sprintf(actionList[actNum++],"%s %s Exitn",nowTime.toString() , nextTime.toString() );
aglist.del( this ); // 从待处理链表 删除此 Agent
result.add( this ); // 加入结果集。
return ;
}
if( pos.rNo==-1 )
{
roomTo.fNo=1; roomTo.rNo=-1;
moveTo( roomTo );
return;
}
roomTo.fNo = pos.fNo;
roomTo.rNo = -1;
moveTo( roomTo );
return;
}
//----------------- 以下处理进楼 -----------------------
roomTo = roomList[nextRoom];
if( pos.fNo==-2 ) // 进楼
{
nextTime.add(30);
sprintf(actionList[actNum++],"%s %s Entryn",nowTime.toString() , nextTime.toString() );
pos.fNo = 1; pos.rNo=-2; // rNo=-2 表示刚进楼，在门口。
return ;
}
if( pos.rNo==-2 ) // 刚进楼，准备访问。
{
if( roomTo.fNo==1 ) // 访问目标在一楼
{
pos.rNo = roomTo.rNo ;
moveTo( roomList[nextRoom] );
} else {
pos.rNo = -1 ;
roomTo.rNo = -1;
moveTo( roomTo ); // 不在一楼，准备进入电梯
}
return ;
}
//---------------- 以下处理 楼内访问 ----------------------
if( pos.fNo!=roomTo.fNo )
{
roomTo.rNo=-1;
moveTo( roomTo );
}
else
moveTo( roomTo );
}
void Execute() // 总调函数，每次选一个触发时间且编号靠前的Agent 执行一步。
{
Agent *p,*cur ;
while( aglist.head!=NULL )
{
nowTime.setTime("24:60:60"); // nowTime 设为最大值
p = cur = aglist.head;
while(cur!=NULL)
{
if( cur->nextTime < nowTime ) { nowTime=cur->nextTime; p=cur; }
cur = cur->next ;
}
p->doAct(); // 被选上的 Agent 执行一步。
}
}
int main()
{
char cd , str_t[10];
while( scanf("%c ",&cd) && cd!='.' )
{
scanf("%s",str_t);
Agent *ag = new Agent(cd,str_t);
aglist.add(ag);
int roomNo , lastTime , i=0;
while( scanf("%dn",&roomNo) && roomNo )
{
scanf("%d",&lastTime);
ag->roomList[i].fNo = roomNo/100;
ag->roomList[i].rNo = roomNo%100;
ag->lastTime[i] = lastTime;
++i;
}
ag->totalRoom = i; // 每个 Agent 所需访问的房间总数
}
Execute(); // 执行调度
Agent *ag = result.head;
while( ag!=NULL )
{
printf("%cn",ag->code);
for( int i=0; i<ag->actNum ; ++i )
printf("%s",ag->actionList[i]);
printf("n");
ag = ag->next;
}
return 0;
}
