Poj Solution 1025

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;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *