这个解法谈不上简洁，它只是正确解决了问题，可以用来验证别的解法。用c++只不过是为了
理清思路，用c去实现应该会更精炼（但也许更抽象）。

//g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3 
//written by ixor (linuxboy_007@hotmail.com)


#include <vector>
#include <map>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cassert>
#include <cstring>

using namespace std;

#define ELEVATOR_ID( resID ) ( ( GET_FLOOR ( resID ) )*100 + 11 )
#define IS_ELEVATOR( resID ) ( ( resID ) % 100 == 11 )
#define IS_ROOM( resID ) ( ( resID ) != RECEPTION_ID && !IS_ELEVATOR( resID ) )
#define RECEPTION_ID 0
#define SAME_FLOOR( resID1, resID2 ) ( (resID1) / 100 == (resID2) / 100 )
#define GET_FLOOR( resID ) ( ( resID ) == RECEPTION_ID ? 1 : ( resID ) / 100 )

int timeInSec(const char *timeStr)
{
	int hour, min, sec;
	sscanf(timeStr, "%d:%d:%d", &hour, &min, &sec);
	return hour * 3600 + min * 60 + sec;
}

void formatTime(char *buff, int time)
{
	int hour, min, sec;
	hour = time / 3600;
	min = (time % 3600) / 60;
	sec = time % 60;
	sprintf(buff, "%02d:%02d:%02d", hour, min, sec);
}

typedef struct VisitEntry_TAG {
	int resID;
	int usingTime;
} VisitEntry;

class ResDescriptor;
class ResMgr;

class Agent {
      public:
	Agent(char pri, const char *timeStr);

	~Agent() {
		while (!descriptionList.empty()) {
			delete descriptionList.back();
			 descriptionList.pop_back();
		}
	} 
	
	int tick(int time);
	
	void printLog( void ){
		DescriptionList::const_iterator iter;
		printf( "%c\n", getPriority() );
		for( iter = descriptionList.begin(); iter != descriptionList.end(); iter ++ ){
			printf( "%s\n", *iter );
		}
	}

	void addVisitEntry(VisitEntry & entry) {
		visitList.push(entry);
	}

	bool isFinished() const {
		return finished;
	} 
	
	char getPriority() const {
		return priority;
    }

    private:
    
	void onGetResource(ResDescriptor * res, int tick);
	void onWaitResource(ResDescriptor * res, int tick);
	void onLoseResource(ResDescriptor * res, int tick);

	typedef enum AgentState_TAG {
		PENDING,
		WAITING,
		HOLDING,
	} AgentState;

	typedef queue < VisitEntry > VisitList;
	typedef vector< char * > DescriptionList;

	void addDescription(const char *buff) {
		int len = strlen(buff) + 1;
		char *des = new char[len];
		strcpy(des, buff);
		descriptionList.push_back(des);
	}

	const VisitEntry & getCurEntry(void) const {
		assert( !visitList.empty() );
		return visitList.front();
	} 
	
	void formatTimeSection(int start, int end) {
		prepareBuff();
		formatTime(word, start);
		strcat(line, word);
		strcat(line, " ");
		formatTime(word, end);
		strcat(line, word);
		strcat(line, " ");
	}

	void popCurEntry(void) {
		assert(visitList.size());
		visitList.pop();
	}

	void prepareBuff(void) {
		line[0] = '\0';
		word[0] = '\0';
		tmpBuff[0] = '\0';
	}

	bool finished;
	ResDescriptor *curRes;
	ResDescriptor *goalRes;

	char state;
	char priority;
	static char line[40];
	static char word[10];
	static char tmpBuff[40];
	static ResMgr *resMgr;
	int wakeUpTime;
	int waitBeginTime;
	VisitList visitList;
	DescriptionList descriptionList;
};

class ResDescriptor {
      public:
	ResDescriptor(int id):
		waitingQue(NULL),
		beginTime(0),
		usingTime(0),
		resID(id) {} 
	
	~ResDescriptor() {
		if (waitingQue)
			delete waitingQue;
	}

	virtual char acquire(Agent * agent, int usingTime_a, int tick) {
		if( queueEmpty() ){
			if( !beginTime ) return giveRes( agent, usingTime_a, tick );

			if( beginTime + usingTime <= tick ) return giveRes( agent, usingTime_a, tick );

			return enque(agent);
		}

		return decideByQuePriority( agent, usingTime_a, tick );
	}

	int getFloor(void) {
		return resID / 100;
	}

	int getBeginTime(void) {
		return beginTime;
	}

	int getUsingTime(void) {
		return usingTime;
	}

	int getID(void) {
		return resID;
	}

	typedef enum ResState_TAG {
		FREE,
		QUEUING
	} ResState;

      protected:

	typedef vector < Agent * >AgentQueue;
	char giveRes( Agent * agent, int usingTime_a, int tick ){
		beginTime = tick;
		usingTime = usingTime_a;
		return FREE;
	}

	char decideByQuePriority( Agent * agent, int usingTime_a, int tick ){
		assert( !queueEmpty() );

		Agent *first = waitingQue->front();
		if( first->getPriority() >= agent->getPriority() ){
			if( !beginTime ){
				if( first->getPriority() == agent->getPriority() ) deque();
			       	return giveRes( agent, usingTime_a, tick );
			}

			if( beginTime + usingTime <= tick ){
				if( first->getPriority() == agent->getPriority() ) deque();
				return giveRes( agent, usingTime_a, tick );
			}
		}
		
		return enque(agent);
	}

	char enque(Agent * agent) {
		if (!waitingQue)
			waitingQue = new AgentQueue();
		AgentQueue::iterator iter;

		for (iter = waitingQue->begin(); iter != waitingQue->end();
		     iter++) {
			if ((*iter)->getPriority() >= agent->getPriority())
				break;
		}
		
		
		if ( !waitingQue->empty() && iter != waitingQue->end() && (*iter)->getPriority() == agent->getPriority() )
			return QUEUING;

		waitingQue->insert(iter, agent);
		return QUEUING;
	}

	void deque() {
		if (waitingQue->size())	waitingQue->erase( waitingQue->begin() );
		else assert(false);
	}

	bool queueEmpty() {
		if (!waitingQue)
			return true;
		return waitingQue->empty();
	}

	AgentQueue *waitingQue;
	int resID;
	int beginTime;
	int usingTime;

};

class RoomDescriptor: public ResDescriptor{
	public:
	RoomDescriptor( int id ):ResDescriptor( id ){ assert( IS_ROOM( id ) ); }
};

class ReceptionDescriptor: public ResDescriptor{
	public:
	ReceptionDescriptor( int id ):ResDescriptor( id ){ assert( id == RECEPTION_ID ); }
	
	char acquire(Agent * agent, int usingTime_a, int tick){
		return FREE;
	}
};

class ElevatorDescriptor:public ResDescriptor{
	public:
	ElevatorDescriptor( int id ):ResDescriptor( id ){ assert( IS_ELEVATOR( id ) ); }
	
	char acquire(Agent * agent, int usingTime_a, int tick){
		if( tick % 5 ) return enque( agent );

		return ResDescriptor::acquire( agent, 5, tick );
	}
	
};


class ResMgr {
      public:
	typedef map < int, ResDescriptor * >ResRecord;

	static ResMgr *instance() {
		if (!s_instance)
			s_instance = new ResMgr();
		return s_instance;
	}
	
	ResDescriptor *getRes(int resID) {
		if (resRec.find(resID) == resRec.end()){
			if( IS_ELEVATOR( resID ) ) resRec[resID] = new ElevatorDescriptor( resID );
			else if( resID == RECEPTION_ID ) resRec[resID] = new ReceptionDescriptor( resID );
			else resRec[resID] = new RoomDescriptor(resID);
		}
		return resRec[resID];
	}

	~ResMgr() {
		ResRecord::iterator iter;
		for (iter = resRec.begin(); iter != resRec.end(); iter++) {
			delete iter->second;
		}
	}

      private:
	ResMgr() {
	}

	ResRecord resRec;

	static ResMgr *s_instance;
};

ResMgr *ResMgr::s_instance = NULL;

class AgentMgr {
      public:
	static AgentMgr *instance() {
		if (!s_instance)
			s_instance = new AgentMgr();
		return s_instance;
	} 
	
	bool isFinished(void)const {
		AgentAry::const_iterator iter;

		for (iter = agents.begin(); iter != agents.end(); iter++) {
			if (!(*iter)->isFinished())
				return false;
		} 
		
		return true;
	}

	void addAgent(Agent * agent) {
		AgentAry::iterator iter;

		for (iter = agents.begin(); iter != agents.end(); iter++) {
			if ((*iter)->getPriority() > agent->getPriority())
				break;
		}
		agents.insert(iter, agent);
	}

	Agent *getAgent(int idx) const {
		assert(idx >= 0 && idx < getAgentNum());

		return agents[idx];
	} 
	
	int getAgentNum() const {
		return agents.size();
     	} 
      
      private:
	typedef vector < Agent * >AgentAry;
	static AgentMgr *s_instance;
	AgentAry agents;
};

AgentMgr *AgentMgr::s_instance = NULL;

Agent::Agent(char pri, const char *timeStr):finished(false),
priority(pri), curRes(NULL), goalRes(NULL), state(PENDING), waitBeginTime(0)
{
	wakeUpTime = timeInSec(timeStr);

	goalRes = resMgr->getRes(RECEPTION_ID);
}

int Agent::tick(int time)
{
	if (time != wakeUpTime)
		return wakeUpTime;

	if (curRes && state == HOLDING) {
		onLoseResource(curRes, time);
		curRes = NULL;
		return wakeUpTime;
	}

	int resState;
	if (goalRes->getID() == RECEPTION_ID)
		resState = goalRes->acquire(this, 0, time);
	else if( IS_ELEVATOR( goalRes->getID() ) )
		resState = goalRes->acquire(this, 0, time);
	else
		resState = goalRes->acquire(this, getCurEntry().usingTime, time);

	switch (resState) {
	case ResDescriptor::FREE:
		if (state == WAITING) {
			formatTimeSection(waitBeginTime, time);
			if (IS_ELEVATOR(goalRes->getID()))
				sprintf(tmpBuff, "Waiting in elevator queue");
			else
				sprintf(tmpBuff,
					"Waiting in front of room %04d",
					goalRes->getID());
			strcat(line, tmpBuff);
			addDescription(line);
			waitBeginTime = 0;
		}
		onGetResource(goalRes, time);
		state = HOLDING;
		break;

	case ResDescriptor::QUEUING:
		if (state != WAITING) {
			waitBeginTime = time;
			state = WAITING;
		}
		onWaitResource(goalRes, time);
		break;

	default:
		assert(false);
		break;
	}

	return wakeUpTime;
}

void Agent::onGetResource(ResDescriptor * res, int tick)
{
	if (res->getID() == RECEPTION_ID) {
		formatTimeSection(tick, tick + 30);
		strcat(line, "Entry");
		addDescription(line);
		wakeUpTime += 30;
	} else {
		if( IS_ELEVATOR( res->getID() ) ){
			int stayTime;
			if( visitList.empty() ){
				stayTime = ( GET_FLOOR( goalRes->getID() ) - 1 ) * 30;
				assert( stayTime > 0 );
			} else {
				stayTime = abs( GET_FLOOR( goalRes->getID() ) - GET_FLOOR( getCurEntry().resID ) ) * 30;
			}
			formatTimeSection(tick, tick + stayTime );
			sprintf(tmpBuff, "Stay in elevator");
			wakeUpTime += stayTime;
		}else{
			formatTimeSection(tick, tick + getCurEntry().usingTime);
			sprintf(tmpBuff, "Stay in room %04d", res->getID());
			wakeUpTime += getCurEntry().usingTime;
		}
		strcat(line, tmpBuff);
		addDescription(line);
	}

	curRes = res;
}

void Agent::onWaitResource(ResDescriptor * res, int tick)
{
	if( IS_ELEVATOR( res->getID() ) ){
		wakeUpTime = tick + 5 - tick % 5;
		return;
	}

	wakeUpTime = res->getBeginTime() + res->getUsingTime();
	assert( wakeUpTime > tick );
}

void Agent::onLoseResource(ResDescriptor * res, int tick)
{
	if (res->getID() == RECEPTION_ID) {
		if (GET_FLOOR(getCurEntry().resID) == 1) goalRes = resMgr->getRes(getCurEntry().resID);
		else goalRes = resMgr->getRes(ELEVATOR_ID(RECEPTION_ID));
		
		return;
	}
	
	if( IS_ELEVATOR( res->getID() ) ){
		if( visitList.empty() ) goto EXIT;
		formatTimeSection(tick, tick + 10);
		sprintf( tmpBuff, "Transfer from elevator to room %04d", getCurEntry().resID );
		strcat( line, tmpBuff );
		addDescription( line );
		goalRes = resMgr->getRes( getCurEntry().resID );
		wakeUpTime += 10;
	}else{
		popCurEntry();
		if( visitList.empty() ){
			if( GET_FLOOR( curRes->getID() ) == 1 ){
EXIT:
				formatTimeSection( tick, tick + 30 );
				strcat( line, "Exit" );
				addDescription( line );
				finished = true;
				return;
			}

			formatTimeSection( tick, tick + 10 );
			sprintf( tmpBuff, "Transfer from room %04d to elevator", curRes->getID() );
			strcat( line, tmpBuff );
			addDescription( line );
			goalRes = resMgr->getRes( ELEVATOR_ID( curRes->getID() ) );
			wakeUpTime += 10;
			return;
		}

		
		formatTimeSection(tick, tick + 10);
		if (SAME_FLOOR(getCurEntry().resID, curRes->getID())) {
			sprintf(tmpBuff, "Transfer from room %04d to room %04d",
				curRes->getID(), getCurEntry().resID);
			strcat(line, tmpBuff);
			addDescription(line);
			goalRes = resMgr->getRes(getCurEntry().resID);
			wakeUpTime += 10;
		} else {
			sprintf(tmpBuff, "Transfer from room %04d to elevator",
				curRes->getID());
			strcat(line, tmpBuff);
			addDescription(line);
			goalRes = resMgr->getRes(ELEVATOR_ID(curRes->getID()));
			wakeUpTime += 10;
		}
	}
}
ResMgr *Agent::resMgr = ResMgr::instance();
char Agent::line[] = { '\0' };
char Agent::tmpBuff[] = { '\0' };
char Agent::word[] = { '\0' };

void action(int startTime)
{
	int t, idx;
	int nearestWakeUp = -1;
	int wakeUp;
	AgentMgr *agentMgr = AgentMgr::instance();
	Agent *agent;

	for (t = startTime; !agentMgr->isFinished(); t = nearestWakeUp) {
		nearestWakeUp = -1;
		for (idx = 0; idx < agentMgr->getAgentNum(); idx++) {
			agent = agentMgr->getAgent(idx);
			if( agent->isFinished() ) continue;
			wakeUp = agent->tick(t);
			if( nearestWakeUp == -1 || wakeUp < nearestWakeUp ) nearestWakeUp = wakeUp;
			
			//printf("tick:%d\n", t);
			//agent->printLog();
		}
	}
	
	for( idx = 0; idx < agentMgr->getAgentNum(); idx ++ ){
		agent = agentMgr->getAgent( idx );
		agent->printLog();
		printf("\n");
	}
}

int main(void)
{
	int n;
	char buff[15];
	Agent *curAgent;
	int resourceID;
	int time;
	int startTime = -1;
	char priority;
	VisitEntry entry;
	AgentMgr *agentMgr = AgentMgr::instance();
	
	//FILE *stdin;
	//stdin = fopen( "data.txt", "r" );
	
	while (true) {
		fscanf( stdin, "%[^\n]", buff );
		while ( fgetc( stdin ) != '\n') ;

		if (strlen(buff) == 1 && buff[0] == '.')
			break;

		curAgent = new Agent(buff[0], &buff[2]);
		if( startTime == -1 || timeInSec( &buff[2] ) < startTime ) startTime = timeInSec( &buff[2] );

		agentMgr->addAgent(curAgent);

		while (true) {
			fscanf( stdin, "%[^\n]", buff );
			while ( fgetc( stdin ) != '\n' );

			if (strlen(buff) == 1 && buff[0] == '0')
				break;

			sscanf(buff, "%d %d", &resourceID, &time);

			entry.resID = resourceID;
			entry.usingTime = time;
			curAgent->addVisitEntry(entry);
		}
	}
	
	//fclose(stdin);
	action( startTime );

	return 0;
}

• Re:此题关键点说明（附代码） (15116) SDRJ102010010367 2012-04-25 15:43:33