【POJ 1025 Department 解題報告】

心血來潮做了老師布置的一道ACM題，思前想後，加之老師的引導才弄出結果來，不過做完之後發現一個老結論——問題都是在解決之前很困難，解決之後你會發現,喔~原來是這樣....現在下筆記之，隻為了提高一下自己的語言即邏輯組織能力，别無它用...

【1樓____題目】

【2樓____題意簡析】

【3樓____題目流程邏輯化】

【4樓____資料結構分析】

【5樓____題目關鍵細節分析】

【6樓____程式實作思路】

【7樓____通路流程部分的源代碼】

//------------------------------------------------1st floor--------------------------------------------------

【題目】

http://poj.org/problem?id=1025

//------------------------------------------------2nd floor--------------------------------------------------

【題意簡析】

故事背景：

他們說有一棟總部大樓，每天有若幹名神秘人員要進入總部去各個房間呆呆，然後，悄無聲息地離開......好冷....進入正題

題意簡析：

有一個10層的總部大樓，每層樓有10個房間以及1部電梯（這裡強調下，差別于我們日常生活中常見的各類電梯，本總部的電梯比較理想，5秒一班，隻要你欲乘上電梯的時間是5的倍數即可搭乘，另一特殊情況5樓詳述）。

每天有若幹通路者要進入大樓對樓中某些房間進行通路并在房中停留一段時間，最後離開大樓。

每個通路者都有自己的唯一辨別，由字母A~Z表示，字母越靠前，該通路者優先級越高。

每個房間及電梯在同一時間隻能進一個人，如果有多名人員要通路同一個房間或電梯，他們必須在外排隊，排隊的标準是：優先級越高的通路者越靠前。

每個通路者都先進入大樓（即1樓），找接待員拿自己的通路清單（該清單記錄了此人在不受任何影響情況下的初始通路流程）。

每個通路者都以清單中樓層以及房間号的升序周遊房間，如從0101開始到0206，如果欲通路的房間中有人，他就必須在外等待，而非跳過本房間去下一個房間。

在完成最後一個房間的通路後，通路者們離開大樓（如果不在1樓，通路者們要通過電梯降到1樓，然後離開大樓）

時間細節：

通路者進入總部大樓，得到接待員給的通路清單，到達電梯前或者到達第一層的指定房間，需要30秒。

離開總部大樓，即從一樓的電梯出來或者從一樓的房間裡出來經過接待員走出總部大樓需要30秒。

同一層樓時，從電梯到指定房間或者指定房間前的排隊隊列；同一層樓時，從房間走到電梯裡或者電梯前的排隊隊列；同一層樓時，從一個房間出來走到另一個房間或者另一個房間前的排隊隊列，都需要10秒鐘。

使用電梯上、下一層，需要30秒。

輸入資料：

A 10:00:00 //通路者辨別及其進入大樓的開始時間

0101 100 //通路者欲通路的樓層房間号及欲在其中停留的時間

0110 50

0202 90

0205 50

0 //某一個通路者的資料結束标記

B 10:00:00

0101 20

. //整個輸入資料結束标記

輸出資料：

按通路者優先級由高到低輸出每個通路者詳細的通路流程，第一排是通路者辨別，以後每排輸出一個流程，最後以空白行結束。

流程描述有以下語句：

Entry

Waiting in elevator queue

Waiting in front of room xxyy

Transfer from room xxxx to room xxyy

Transfer from elevator to room xxyy

Transfer from room xxyy to elevator

Stay in room xxyy

Stay in elevator

Exit

具體如：

10:00:00 10:00:30 Entry

10:00:30 10:02:10 Stay in room 0101

10:02:10 10:02:20 Transfer from room 0101 to room 0110

10:02:20 10:03:10 Stay in room 0110

10:03:10 10:03:20 Transfer from room 0110 to elevator

10:03:20 10:03:50 Stay in elevator

10:03:50 10:04:00 Transfer from elevator to room 0202

10:04:00 10:05:30 Stay in room 0202

10:05:30 10:05:40 Transfer from room 0202 to room 0205

10:05:40 10:07:40 Waiting in front of room 0205

10:07:40 10:08:30 Stay in room 0205

10:08:30 10:08:40 Transfer from room 0205 to elevator

10:08:40 10:09:10 Stay in elevator

10:09:10 10:09:40 Exit

輸入輸出詳見原題

//------------------------------------------------3rd floor--------------------------------------------------

【題目流程邏輯化】

現在将題目描述的通路流程提煉成邏輯流程。

通過對題意的解析，不難發現對于一個通路者來說，我們能夠提煉出以下9個基本邏輯事件：

①進入大樓

②等待電梯

③等待進入房間

④從房間走到房間（指同樓層的房間）

⑤從電梯走到指定房間

⑥從房間走到電梯

⑦呆在房間中

⑧在電梯中

⑨離開大樓

對于上述分析，我們可以列出一個事件表格，并對其标以事件類型以便程式實作

事件描述

事件類型

執行時間/s

進入大樓

等待電梯

依情況而定

等待進入房間

依情況而定

從房間走到房間

從電梯走到房間

從房間走到電梯

呆在房間中

輸入資料

在電梯中

30/層

離開大樓

整個通路者通路流程中隻有這9基本邏輯事件，通路者們根據自己的初始資料開始通路，通路過程中由于其他通路者的互相影響（即指同時通路電梯或房間時的排隊現象）不斷修改自己的通路計劃，直至最終完成通路離開總部大樓。

<b>//------------------------------------------------4th floor--------------------------------------------------</b>

【資料結構分析】

根據前述，不難看出本題重點在排隊和通路者的通路清單。

由于排隊是按照通路者的優先級别決定哪個靠前，是以可以使用以通路者優先級為判定标準的優先隊列。

由于通路者的通路清單中欲通路房間的數目不明，是以使用連結清單儲存各通路者的通路清單，一個節點儲存該通路者一個事件（指上述9個事件中的一個）

//------------------------------------------------5th floor--------------------------------------------------

【題目關鍵細節分析】

細節①：如何處理電梯等待事件

由于本題電梯比較理想，是以我們隻需要考慮通路者進入電梯的時間是否5的倍數，若不是，則需再等若幹秒直到滿足條件。

然而若有兩名及以上通路者需要同時進入電梯，則需按照他們的優先級依次進入，是以排在後面的一個通路者就要多等上5秒鐘（因為此時前一個優先級高的通路者剛進電梯，此時本通路者無法進入電梯，隻能再等5秒）

細節②：如何表示電梯

由于大樓中有房間與電梯兩種物件，但實際上他們都是容器，用來裝人的，是以可以把電梯視為一種特殊的房間，按照表示房間的方式表示即可，處理時按照處理電梯的方式處理即可。即房間号從01~10，我們用00号表示電梯，如0300表示3樓的電梯。

//------------------------------------------------6th floor--------------------------------------------------

【程式實作思路】

這裡給出實作整個過程的思路，具體實作因人而異，我把這題當練習資料結構來做的，是以包括優先隊列類在内的幾乎所有函數子產品都是自己編碼實作，大大增加了代碼量，很多都可以直接用STL或标準庫函數。

①事件表格的程式表示

//事件枚舉類型

enum EventType

{

et_entry,

et_wait_elevator,

et_wait_front_room,

et_room2room,

et_elevator2room,

et_room2elevator,

et_in_room,

et_in_elevator,

et_exit

};

const size_t event_time[] = {30,5,0,10,10,10,0,30,30};

event_time[et_wait_front_room] 即為等待進入房間的初始時間，由于初始化時不會有通路者的排隊情況，是以此項的值為0

②事件結構體及通路者事件連結清單

事件結構體擁有通路者标記，本事件開始時間，本事件持續時間，本事件的事件類型，本事件的起始地點，本事件的目的地點六個資料項

(這裡我做複雜了，string 類型可以直接用int型資料合理替換的，我為了表示友善，選擇了string，有時間再改過)

通路者事件連結清單節點擁有事件資料域以及一個指向下一節點的指針

//事件結構體

struct Event

char _visitor_id; //通路者标号

string _start_time; //事件開始時間

size_t _duration_time; //事件持續時間

EventType _event_type; //事件類型

string _from; //起始地點

string _to; //目的地點

//通路者行程表節點

struct Schedule

Schedule *next;

Event eve;

③由于整個流程隻有9個邏輯事件，是以，我們獨立出9個子產品以便将對應事件追加到對應通路者的通路連結清單末尾，通過一個初始化過程，調用這9個子產品，初始化每個通路者的通路連結清單。

string Entry(string start_time, string id, Schedule *head);

string WaitElevator(string start_time, Schedule *head);

string WaitFrontRoom(string start_time, string to, Schedule *head);

string RoomToRoom(string start_time, string to, Schedule *head);

string ElevatorToRoom(string start_time, string to, Schedule *head);

string RoomToElevator(string start_time, string to, Schedule *head);

string InRoom(string start_time, string to, size_t duration_time, Schedule *head);

string InElevator(string start_time, string to, Schedule *head);

void Exit(string start_time, Schedule *head);

以上9個子產品除了Exit可能(即通路者離開時不在1樓)調用WaitElevator以及RoomToElevator之外，其餘子產品都獨立運作，将該子產品對應的新事件節點追加到對應通路者的通路連結清單末尾，并傳回本次事件的結束時間，以作為其餘子產品的參數傳遞（即下一個事件的開始時間）。

④初始化通路者連結清單

根據輸入資料，初始化所有通路者的行程連結清單

//所有通路者存入一個vector，每個vector元素首為一個通路者通路連結清單頭結點

void InitSchedule(vector<Schedule*> &visitors_schedule)

⑤處理初始化後的通路者連結清單

由于通路過程中可能存在等待事件，是以我們必須針對等待事件酌情更新等待之後的所有事件的開始時間，若遇到等待電梯事件，更新開始時間時還要考慮其是否5的倍數。

⑥輸出通路者的詳細行程

這裡強調下，由于題目并沒有說輸入資料是按字母順序排列的，但是要求了輸出的結果要按升序排列，是以輸出時還要對vector中所有連結清單按其通路者辨別字母由小到大排序後再輸出

//------------------------------------------------7th floor--------------------------------------------------

【通路流程部分的源代碼】

以下是整個流程的源代碼，由于我用的string類型表示HH:MM:SS的時間，是以多了許多轉換過程，以及其他輔助函數，這裡就不一一列舉了。

#include"event.h"

//行程表節點比較函數

bool Less(void *x, void *y);

//全體優先隊列數組([有效樓層01~10，00号樓層為特殊值，不予計算][有效房間00~10])

PQueue<Schedule*,Less> queues[kFloorCount][kRoomCount];

* 子產品功能：行程表節點的比較

* 子產品傳回：若x小于y，傳回true，否則false

bool Less(void *x, void *y)

if(TimeCmp((*(Schedule**)(x))->eve._start_time,(*(Schedule**)(y))->eve._start_time) == -1)

return true;

else if(TimeCmp((*(Schedule**)(x))->eve._start_time,(*(Schedule**)(y))->eve._start_time) == 0

&& (*(Schedule**)(x))->eve._visitor_id < (*(Schedule**)(y))->eve._visitor_id)

return false;

}

* 子產品功能：得到指向行程連結清單尾節點的指針

Schedule* GetLastNode(Schedule *head)

for( ;head->next != NULL; )

head = head->next;

return head;

* 子產品功能：根據通路者進入大樓事件設定通路者行程連結清單

* 子產品傳回：子產品傳回本次事件完成之後的時間，作為後續事件的開始時間

string Entry(string start_time, string id, Schedule *head)

Schedule *new_schedule = new Schedule;

assert(new_schedule != NULL);

new_schedule->next = NULL;

new_schedule->eve._visitor_id = id[0];

new_schedule->eve._start_time = start_time;

new_schedule->eve._duration_time = event_time[et_entry];

new_schedule->eve._event_type = et_entry;

new_schedule->eve._from = "0000";

new_schedule->eve._to = "0000";

//将本事件追加到事件連結清單尾

GetLastNode(head)->next = new_schedule;

//傳回本次事件結束時間以作為後續事件的開始時間

return GetTime(new_schedule->eve._start_time,new_schedule->eve._duration_time);

* 子產品功能：根據通路者等待電梯事件設定通路者行程連結清單

string WaitElevator(string start_time, Schedule *head)

new_schedule->eve._visitor_id = head->next->eve._visitor_id;

new_schedule->eve._event_type = et_wait_elevator;

new_schedule->eve._from = GetLastNode(head)->eve._to;

if(new_schedule->eve._from == "0000")

new_schedule->eve._from[1] = '1';

new_schedule->eve._to = new_schedule->eve._from;

//計算等待時間

size_t waiting_time = event_time[et_wait_elevator];

size_t start_seconds = CStr2Int(start_time.substr(6,2).c_str());

if(start_seconds % waiting_time == 0)

new_schedule->eve._duration_time = 0;

else

new_schedule->eve._duration_time = waiting_time - start_seconds % waiting_time;

//将本次電梯等待事件加入對應樓層的電梯等待隊列中

queues[CStr2Int(new_schedule->eve._from.substr(0,2).c_str())][0].push(new_schedule);

* 子產品功能：根據通路者等待進入房間事件設定通路者行程連結清單

string WaitFrontRoom(string start_time, string to, Schedule *head)

new_schedule->eve._duration_time = event_time[et_wait_front_room];

new_schedule->eve._event_type = et_wait_front_room;

new_schedule->eve._to = to;

//将本事件加入對應房間等待隊列

queues[CStr2Int(to.substr(0,2).c_str())][CStr2Int(to.substr(2,2).c_str())].push(new_schedule);

* 子產品功能：根據通路者從同一樓層的一個房間走到另一個房間事件設定通路者行程連結清單

string RoomToRoom(string start_time, string to, Schedule *head)

new_schedule->eve._event_type = et_room2room;

new_schedule->eve._duration_time = event_time[et_room2room];

* 子產品功能：根據通路者從同一樓層的電梯裡走到房間事件設定通路者行程連結清單

string ElevatorToRoom(string start_time, string to, Schedule *head)

new_schedule->eve._event_type = et_elevator2room;

new_schedule->eve._from[2] = '0';

new_schedule->eve._from[3] = '0';

new_schedule->eve._duration_time = event_time[et_elevator2room];

* 子產品功能：根據通路者從同一樓層的房間裡走到電梯中事件設定通路者行程連結清單

string RoomToElevator(string start_time, string to, Schedule *head)

new_schedule->eve._event_type = et_room2elevator;

new_schedule->eve._duration_time = event_time[et_room2elevator];

string InRoom(string start_time, string to, size_t duration_time, Schedule *head)

new_schedule->eve._event_type = et_in_room;

new_schedule->eve._duration_time = duration_time;

return GetTime(new_schedule->eve._start_time,duration_time);

string InElevator(string start_time, string to, Schedule *head)

new_schedule->eve._event_type = et_in_elevator;

string from = new_schedule->eve._from = GetLastNode(head)->eve._to;

if(from == "0000")

from[1] = '1';

//計算在電梯裡呆的時間

new_schedule->eve._duration_time = (abs(CStr2Int(new_schedule->eve._to.substr(0,2).c_str())

- CStr2Int(from.substr(0,2).c_str()))

) * event_time[et_in_elevator];

* 子產品功能：根據通路者離開大樓事件設定通路者行程連結清單

void Exit(string start_time, Schedule *head)

new_schedule->eve._duration_time = event_time[et_exit];

new_schedule->eve._event_type = et_exit;

//若通路者此時不在1樓，計算其到達1樓的時間

int floor = CStr2Int(new_schedule->eve._from.substr(0,2).c_str());

if(floor != 1 && floor != 0)

{

string elevator = new_schedule->eve._from.substr(0,2);

elevator += "00";

start_time = RoomToElevator(start_time,elevator,head);

start_time = WaitElevator(start_time,head);

start_time = InElevator(start_time,"0100",head);

}

* 子產品功能：根據input檔案初始化所有通路者通路事件連結清單

ifstream fin("input.txt",ofstream::in);

if(!fin)

exit(1);

while(true)

{//1次循環初始化完成1個通路者行程連結清單

string id;

string start_time;

fin>>id;

if(id == ".")

break;

fin>>start_time;

Schedule *head = new Schedule;

assert(head != NULL);

head->next = NULL;

visitors_schedule.push_back(head);

head = visitors_schedule.back();

start_time = Entry(start_time,id,head);

while(true)

{//建構本通路者的通路事件連結清單

string room;

size_t duration_time;

fin>>room;

if(room == "0")

{

Exit(start_time,head);

break;

}

fin>>duration_time;

Schedule *cur_schedule = GetLastNode(head);

if(cur_schedule->eve._to.substr(0,2) == room.substr(0,2)

|| ((cur_schedule->eve._event_type == et_entry) && room.substr(0,2) == "01"))

{//目前位置與目的地同層

if(!(cur_schedule->eve._event_type == et_entry))

{//并非剛進入大樓

start_time = RoomToRoom(start_time,room,head);

}

else

{//目前位置與目的地不同層

cur_schedule = GetLastNode(head);

string elevator = cur_schedule->eve._to.substr(0,2);

elevator += "00";

start_time = RoomToElevator(start_time,elevator,head);

start_time = WaitElevator(start_time,head);

start_time = InElevator(start_time,room,head);

start_time = ElevatorToRoom(start_time,room,head);

start_time = WaitFrontRoom(start_time,room,head);

start_time = InRoom(start_time,room,duration_time,head);

}

* 子產品功能：将行程表向量以通路者優先級由高到低重新排序

void SortById(vector<Schedule*> &visitors_schedule)

assert(visitors_schedule.size() > 0);

for(vector<Schedule*>::size_type i=0; i!=visitors_schedule.size()-1; ++i)

vector<Schedule*>::size_type j = i + 1;

Schedule* key = visitors_schedule[j];

while(j>0 && visitors_schedule[j-1]->next->eve._visitor_id > key->next->eve._visitor_id)

{

visitors_schedule[j] = visitors_schedule[j-1];

--j;

visitors_schedule[j] = key;

* 子產品功能：銷毀行程表

void DestroySchedule(vector<Schedule*> &visitors_schedule)

for(vector<Schedule*>::iterator it=visitors_schedule.begin();

it != visitors_schedule.end();

++it)

delete (*it);

visitors_schedule.clear();

* 子產品功能：将所有通路者的行程表輸出到檔案

void OutputSchedule(vector<Schedule*> &visitors_schedule)

//各種事件消息

const string msg[] = {"Entry",

"Waiting in elevator queue",

"Waiting in front of room xxxx",

"Transfer from room xxxx to room xxxx",

"Transfer from elevator to room xxxx",

"Transfer from room xxxx to elevator",

"Stay in room xxxx",

"Stay in elevator",

"Exit"

};

ofstream fout("output",ofstream::out);

//将行程表向量以通路者優先級由高到低重新排序

SortById(visitors_schedule);

vector<Schedule*>::size_type index = 0;

if(index == visitors_schedule.size())

Schedule *idx = visitors_schedule[index]->next;

fout<<idx->eve._visitor_id<<endl;

if(idx == NULL)

if(idx->eve._start_time == GetTime(idx->eve._start_time,idx->eve._duration_time))

idx = idx->next;

continue;

fout<<idx->eve._start_time<<' '

<<GetTime(idx->eve._start_time,idx->eve._duration_time)<<' ';

EventType type = idx->eve._event_type;

string message = msg[type];

if(type == et_wait_front_room)

room = idx->eve._to;

message.erase(25);

message += room;

else if(type == et_room2room)

room = idx->eve._from;

message.erase(19,4);

message.insert(19,room);

message.erase(32);

else if(type == et_elevator2room)

message.erase(31);

else if(type == et_room2elevator)

//Transfer from room xxxx to elevator

else if(type == et_in_room)

message.erase(13);

fout<<message<<endl;

idx = idx->next;

fout<<endl;

++index;

* 子產品功能：行程表處理過程，根據各通路者的原始行程表，考慮他們之間的互相影響

* 形成所有通路者的最終行程表

void ProcessSchedule(void)

//隊首優先隊列，用于得到所有隊首中最小者

PQueue<Schedule*,Less> queues_top;

//儲存上一次出隊的隊首的矩陣

Schedule *pre_top[kFloorCount][kRoomCount] = {NULL};

//得到所有隊列中共有多少個事件

size_t total_event = 0;

for(size_t i=1; i!=kFloorCount; ++i)

for(size_t j=0; j!=kRoomCount; ++j)

total_event += queues[i][j].size();

//調整所有通路者的行程表，直到所有等待隊列為空

if(total_event == 0)

//将所有隊首入優先隊列，進而得到目前所有隊首的最小者

queues_top.clear();

for(size_t i=1; i!=kFloorCount; ++i)

for(size_t j=0; j!=kRoomCount; ++j)

if(!queues[i][j].empty())

queues_top.push(queues[i][j].top());

//計算最小事件在隊列數組中的下标

size_t floor = CStr2Int(queues_top.top()->eve._to.substr(0,2).c_str());

size_t room = CStr2Int(queues_top.top()->eve._to.substr(2,2).c_str());

//事件時間調整标記，未經調整為false

bool delayed = false;

//若本隊列不是第一次出隊,更新本次等待事件的延遲時間

Schedule *pre_event = pre_top[floor][room];

if(pre_event != NULL)

Schedule *cur_event = queues_top.top();

//本次最小事件是等待電梯

if(cur_event->eve._event_type == et_wait_elevator)

//若本次等待電梯事件的開始時間與上一次隊首的開始時間相同，則需再等5秒

if(cur_event->eve._start_time == pre_event->eve._start_time)

{

cur_event->eve._duration_time = pre_event->eve._duration_time + event_time[et_wait_elevator];

delayed = true;

else //最小事件是等待進入房間，更新此事件的等待時間

//計算上一個隊首離開房間的時間

string exit_room_time = GetTime(pre_event->next->eve._start_time,

pre_event->next->eve._duration_time);

int time_sub = TimeSub(exit_room_time,GetTime(cur_event->eve._start_time,

cur_event->eve._duration_time));

//上一次的隊首仍在房中

if(time_sub > 0)

cur_event->eve._duration_time += time_sub;

//隻要延時了，則維護本次事件之後的所有事件的時間連貫性，并維護對應堆性質

if(delayed)

//算法描述：本次事件之後的事件的開始時間依次加上上一次事件的等待時間

// 若下一次事件是電梯等待事件，則還要調整本次事件的等待時間

// 以滿足本次事件結束（即進入電梯）的時間是5的倍數

while(true)

//得到下一事件

Schedule *next_event = cur_event->next;

if(next_event == NULL)

break;

//更新下一事件的開始時間

next_event->eve._start_time = GetTime(cur_event->eve._start_time,cur_event->eve._duration_time);

//若下一次次事件是電梯等待事件，則還需需更新電梯等待時間，以滿足5秒要求

if(next_event->eve._event_type == et_wait_elevator)

{

//重新計算下一事件的等待時間

next_event->eve._duration_time = 0;

size_t waiting_time = event_time[et_wait_elevator];

size_t start_seconds = CStr2Int(next_event->eve._start_time.substr(6,2).c_str());

if(start_seconds % waiting_time != 0)

next_event->eve._duration_time = (waiting_time - (start_seconds % waiting_time));

}

//計算本事件所在樓層即房間

size_t floor = CStr2Int(cur_event->eve._to.substr(0,2).c_str());

size_t room = CStr2Int(cur_event->eve._to.substr(2,2).c_str());

//維護本事件所在隊列的堆性質

queues[floor][room].heap_ify();

//更新目前事件

cur_event = cur_event->next;

//該最小事件出隊，并以此更新pre_top對應元素

pre_top[floor][room] = queues[floor][room].pop();

--total_event;

* 子產品功能：模拟整個通路過程

void Visiting(void)

//建立所有通路者的行程表

vector<Schedule*> visitors_schedule;

//初始化所有行程連結清單

InitSchedule(visitors_schedule);

//依據各通路者之間的互相影響，處理初始化後的通路者行程表

ProcessSchedule();

//将行程表輸出到檔案

OutputSchedule(visitors_schedule);

//銷毀行程連結清單

DestroySchedule(visitors_schedule);

【POJ 1025 Department 解題報告】

繼續閱讀

XML document processing in Java using XPath and XSLTXML document processing in Java using XPath and XSLT

【POJ 1025 Department 解題報告】

Citrix User Profile Management 設定參考