acm.pku 1025 Department

http://acm.pku.edu.cn/JudgeOnline/problem?id=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) 
            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; 
    int nTmLen; 
};
 
enum AGSTAT{ENTRY,GOTOROOM,GOTOQ,COMPLETE};
struct Agent
{
    int index; 
    AGSTAT stat;
    char ID;
    int curFloor; 
    TIME tmCur; 
    vector<Event*> vecEvent; 
    queue<Task> QTask; 
    bool operator <(const Agent& ag) const
    {
        return ID<ag.ID;
    }
    bool Init()
    { 
        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()
    { 
        int i=QWait.top();
        vecAg[i].tmCur=vecAg[i].vecEvent[vecAg[i].vecEvent.size()-1]->tmEnd=tmCur;
        QWait.pop();
        return i;
    }
};
 
Room room[11]; 
priority_queue<int,vector<int>,AgTimeIDLess> QAgWait; 
priority_queue<int,vector<int>,AgFloorLess> QAgOthflo; 
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);
}
 
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()
{ 
    Task task=QTask.front();
    if(task.floor!=curProcFloor&&task.roomId!=0)
    {
        QAgOthflo.push(index); 
        return;
    }
    stat=GOTOROOM;
     
    if (task.roomId==0&&room[task.roomId].QWait.empty()&&
        ((tmCur.sec%5)||tmCur<room[task.roomId].tmCur))
    { 
        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) 
    {
        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); 
    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
    { 
        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)
        { 
            int index=room[nRoomIdx].Pop();
            vecAg[index].CheckTask();
        }
        else
        { 
            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;
}
Информатика и математика

Меню навигации

Пользовательские ссылки

Информация о пользователе

acm.pku 1025 Department

Сообщений 1 страница 1 из 1

Поделиться12009-06-17 22:13:11
