poj 1025 Department
Department
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 2367 | Accepted: 586 |
Description
The Department of Security has a new headquarters building. The building has several floors, and on each floor there are rooms numbered xxyy where yy stands for the room number and xx for the floor number, 0 < xx; yy <= 10. The building has `pater-noster' elevator, i.e. elevator build up from several cabins running all around. From time to time the agents must visit the headquarters. During their visit they want to visit several rooms and in each room they want to stay for some time. Due to the security reasons, there can be only one agent in the same room at the same time, The same rule applies to the elevators. The visits are planned in the way ensuring they can be accomplished within one day. Each agent visits the headquarters at most once a day.
Each agent enters the building at the 1st floor, passes the reception and then starts to visit the rooms according to his/her list. Agents always visit the rooms by the increasing room numbers. The agents form a linear hierarchy according to which they have assigned their one letter personal codes. The agents with higher seniority have lexicographically smaller codes. No two agents have the same code.
If more then one agent want to enter a room, or an elevator, the agents have to form a queue. In each queue, they always stand according to their codes. The higher the seniority of the agent, the closer to the top of the queue he stands. Every 5 s (seconds) the first agent in the queue in front of the elevator enters the elevator. After visiting the last room in the headquarters each agent uses if necessary elevator to the first floor and exits the building.
The times necessary to move from a certain point in the headquarters to another are set as follows: Entering the building, i.e. passing the reception and reaching the elevator, or a room on the first floor takes 30 s. Exiting the building, i.e. stepping out of the elevator or a room on the first floor and passing the reception takes also 30 s. On the same floor, the transfer from the elevator to the room (or to the queue in front of the room), or from the room to the elevator (or to the queue in front of the elevator), or from one room to another (or to the queue in front of the room) takes 10 s. The transfer from one floor to the next floor above or below in an elevator takes 30 s. Write a program that determines time course of agent's visits in the headquarters.
Input
The input file contains the descriptions of n >= 0 visits of different agents. The first line of the description of each visit consists of agent's one character code C, C = A, . . ., Z, and the time when the agent enters the headquarters. The time is in the format HH:MM:SS (hours, minutes, seconds). The next lines (there will be at least one) contain the room number, and the length of time intended to stay in the room, time is in seconds. Each room is in a separate line. The list of rooms is sorted according to the increasing room number. The list of rooms ends by the line containing 0. The list of the descriptions of visits ends by the line containing the character dot.
Output
The output contains detailed records of each agent's visit in the headquarters. For each agent, there will be a block. Blocks are ordered in the order of increasing agent's codes. Blocks are separated by an empty line. After the last block there is an empty line too. The first line of a block contains the code of agent. Next lines contain the starting and ending time (in format HH:MM:SS) and the descriptions of his/her activity. Time data will be separated by one blank character. Description will be separated from time by one blank character. Description will have a form Entry, Exit or Message. The Message can be one of the following: Waiting in elevator queue, Waiting in front of room RoomNumber, Transfer from room RoomNumber to room RoomNumber, Transfer from elevator to room RoomNumber, Transfer from RoomNumber to elevator, Stay in room RoomNumber, Stay in elevator.
Sample Input
A 10:00:00
0101 100
0110 50
0202 90
0205 50
0
B 10:01:00
0105 100
0201 5
0205 200
0
.
Sample Output
A
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
B
10:01:00 10:01:30 Entry
10:01:30 10:03:10 Stay in room 0105
10:03:10 10:03:20 Transfer from room 0105 to elevator
10:03:20 10:03:25 Waiting in elevator queue
10:03:25 10:03:55 Stay in elevator
10:03:55 10:04:05 Transfer from elevator to room 0201
10:04:05 10:04:10 Stay in room 0201
10:04:10 10:04:20 Transfer from room 0201 to room 0205
10:04:20 10:07:40 Stay in room 0205
10:07:40 10:07:50 Transfer from room 0205 to elevator
10:07:50 10:08:20 Stay in elevator
10:08:20 10:08:50 Exit
部门
安全部有一座新的总部大楼。该建筑分几层,每层有编号xxyy的房间,yy代表房间号,xx代表楼层号,0 < xx;yy < = 10。该建筑有“pater-noster”电梯,即由周围运行的几间小屋组成的电梯。代理商必须不时地到总部来。在他们访问期间,他们想参观几个房间,每个房间他们想呆一段时间。出于安全考虑,同一房间内只能有一名工作人员,电梯也是如此。这些访问的计划确保能在一天内完成。每个代理每天最多访问一次总部。
每个代理商从一楼进入大楼,经过前台,然后根据自己的名单开始参观房间。代理商总是随着房间数量的增加而光顾房间。这些代理形成了一个线性的层次结构,根据这个结构,他们分配了一个字母的个人代码。资历越高的特工的编码在字典上越小。没有两个探员的密码是一样的。
如果多个代理想要进入一个房间或电梯,则必须形成一个队列。在每个队列中,他们总是按照自己的代码站着。工作人员的资历越高,他就越接近队伍的顶端。每隔5秒,在电梯前排队的第一个人进入电梯。在参观完总部的最后一个房间后,每个代理使用必要的电梯到一楼并离开大楼。
从总部的某一地点移动到另一地点所需的时间如下:进入大楼,即经过接待处到达电梯,或一层的一个房间需要30秒。走出大楼,即走出电梯或一层的房间,经过接待处也需要30秒。在同一层,从电梯到房间(或队列前面的房间),或者从房间到电梯(或队列前面的电梯),或从一个房间到另一个(或队列前面的房间)10。乘坐电梯从一层楼到上下一层楼需要30秒。编写一个程序,确定代理商在总部访问的时间进程。
输入
输入文件包含不同代理的n次>= 0访问的描述。每次访问描述的第一行由座席的一个字符编码C, C = A,…,Z和座席进入总部的时间组成。时间的格式为HH:MM:SS(小时、分钟、秒)。下一行(至少有一行)包含房间号,以及打算待在房间里的时间长度,时间以秒为单位。每个房间都在一条单独的线上。房间列表是根据房间数量的增加来排序的。房间列表以包含0的行结束。访问描述列表以包含字符点的行结束。
输出
输出内容包括各代理商在总部访问的详细记录。对于每个代理,都有一个块。块是按照代理代码的递增顺序排列的。块由空行分隔。在最后一个块之后也有一个空行。代码块的第一行包含代理代码。下一行包含开始和结束时间(格式HH:MM:SS)和他/她的活动描述。时间数据将被一个空白字符隔开。描述与时间之间用一个空白字符隔开。Description将有一个表单入口、退出或消息。消息可以是以下信息之一:在电梯队列中等待,在房间房间号前等待,从房间房间号转移到房间房间号,从电梯转移到房间房间号,从房间号转移到电梯,留在房间房间号,留在电梯。
Sample Input
A 10:00:00
0101 100
0110 50
0202 90
0205 50
0
B 10:01:00
0105 100
0201 5
0205 200
0
.
Sample Output
A
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
B
10:01:00 10:01:30 Entry
10:01:30 10:03:10 Stay in room 0105
10:03:10 10:03:20 Transfer from room 0105 to elevator
10:03:20 10:03:25 Waiting in elevator queue
10:03:25 10:03:55 Stay in elevator
10:03:55 10:04:05 Transfer from elevator to room 0201
10:04:05 10:04:10 Stay in room 0201
10:04:10 10:04:20 Transfer from room 0201 to room 0205
10:04:20 10:07:40 Stay in room 0205
10:07:40 10:07:50 Transfer from room 0205 to elevator
10:07:50 10:08:20 Stay in elevator10:08:20 10:08:50 Exit
题目大意:
有一些特工,在一天里要访问一座大楼。这座大楼里有10层,每层10个房间(按xxyy编号每个房间,xx为楼层,yy为房间号)和1个电梯。每个特工要按顺序访问一些特定的房间,并在各个房间里待一段时间。每个特工在一天的某个时间点到达大楼的1层,然后需要30s的时间进行登记之类的活动。到达30s后可以到达一楼的电梯或到达他想要去的位于1楼的房间门口。大楼的电梯每5s一班,每上升一层或下降一层需要30s。出于安全考虑,每个房间和每层的电梯都同时只运行一个人在内。当有多人在电梯或房间门口需要进入时需要排队。每个特工都有一个唯一的编号(A->Z),编号越小,优先级越高,排队时优先。特工访问完一个房间去往下一个房间的过程中可能需要以下动作:从楼层的一个房间去往该层的另一个房间;从楼层的一个房间去往电梯->(等待电梯)->乘电梯->电梯去往另一层的某房间。当访问完所有需要访问的房间后,若特工在1层,则花30s办理手续,离开。若不在1层,则先下电梯至1层再办手续离开。一个特工一天只访问大楼一次,一天内所有活动都会完成。
各种动作需要的时间总结如下:
Entry:登记->到达1楼电梯或1楼某房间 30s
Exit:从最后一个房间或电梯出来至离开 30s
同一层,出电梯到达某房间(或进等候队列)或出房间到达电梯或出房间到到达另一房间 10s
从一层到另一层成电梯每上一层或下一层需要时间 30s
写一个程序来安排所有特工的活动。
输入:含有n>=0个不同的特工。首先输入该特工的编号,然后是进入大楼的时间。接下来的每行,前四个字符表示要访问的房间号码,后一个整数为该特工要在这个房间停留的时间。以0表示该特工的访问计划输入完毕。以"."表示所有输入结束。
输出:输出每个特工的编号加活动详细安排。
本题是一道很复杂模拟题,虽然不必很复杂的算法设计,但是代码量很大,需要精心的设计,也是参考了别人的实现。
定义一个枚举类型表示每个特工当前所处的状态。
enum Event {
et_entry, et_wait_elevator, et_wait_room, et_room2room, et_elevator2room,
et_room2elevator, et_in_room, et_in_elevator, et_exit
};
把电梯看做一个特殊的房间,给予编号XX00。
为每一个房间准备一个等候队列,保存某时刻该房间的等候的特工。
每秒钟遍历每个特工和每个房间,更新特工、房间、电梯的状态。(每次到达电梯口或房间门口就将特工插入对应的等待队列,即使不需要等待,因为只要在输出时过滤掉等待0秒的过程即可。当房间或电梯可以让人进入时选择队列中优先级最高的让其进入。)具体见代码和注释。
代码:
#include
#include
#include
#include
using namespace std;
enum Event {
et_entry, et_wait_elevator, et_wait_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};
class Room {
public:
bool o;
int free_time;
bool waiting_queue[26];
int waiting_cnt;
bool waiting_q_empty() {
return waiting_cnt == 0 ? true :false;
}
void push(int agent_id) {
waiting_queue[agent_id] = true;
++waiting_cnt;
}
int pop() {
for (int i = 0; i < 26; ++i) {
if (waiting_queue[i] == true) {
waiting_queue[i] = false;
--waiting_cnt;
return i;
}
}
}
};
Room room[11][11];
int current_time;
class Plan {
public:
pairp;
Plan * next;
};
class Schedule {
public:
Event e;
int start_time;
int end_time;
int from;
int to;
Schedule * next;
Schedule () {
from = 0;
to = 0;
next = NULL;
}
};
class Agent {
public:
bool e; //是否存在该Agent
int id;
int entry_time;
int exit_time;
Plan * plan;
Schedule * schedule;
void push_plan(pairp) {
Plan * pl = new Plan;
Plan * pt;
pl->p = p;
pl->next = NULL;
if (plan == NULL) {
plan = pl;
return;
}
for (pt = plan; pt->next != NULL; pt = pt->next) ;
pt->next = pl;
}
pairpopr_plan() {
return plan->p;
}
pairpop_plan() {
pairpp = plan->p;
plan = plan->next;
return pp;
}
void push_schedule(Schedule * s) {
Schedule * ps;
if (schedule == NULL) {
schedule = s;
s->next = NULL;
return;
}
for (ps = schedule; ps->next != NULL; ps = ps->next) ;
ps->next = s;
s->next = NULL;
}
Schedule * popr_schedule() {
Schedule * ps;
for (ps = schedule; ps->next != NULL; ps = ps->next) ;
return ps;
}
};
Agent agent[26];
void enqueue(int agent_id, int room_id) {
Schedule * s = new Schedule;
int floor = room_id / 100;
int id = room_id % 100;
room[floor][id].push(agent_id);
if (id == 0) {
s->e = et_wait_elevator;
} else {
s->e = et_wait_room;
}
s->start_time = current_time;
s->end_time = room[floor][id].free_time > current_time ? room[floor][id].free_time : current_time;
s->from = room_id;
if (agent[agent_id].plan == NULL) {
s->to = -1;
} else {
s->to = agent[agent_id].popr_plan().first;
}
agent[agent_id].push_schedule(s);
}
void process(int agent_id) {
Schedule * s = agent[agent_id].popr_schedule();
int from = s->from;
int to = s->to;
int floor = to / 100;
int id = to % 100;
switch (s->e) {
case et_entry:
//第一个房间在1楼,则已到达该房间
if (floor == 1) {
//插入房间等待队列
enqueue(agent_id, to);
} else {
//第一个房间在楼上,则已到达电梯,插入该电梯等候队列
enqueue(agent_id, 100);
}
break;
case et_wait_elevator:
//留在电梯等候队列
break;
case et_wait_room:
//留在房间等候队列
break;
case et_room2room:
//到达房间,插入房间等候队列
enqueue(agent_id, to);
break;
case et_elevator2room:
//到达房间,插入房间等候队列
enqueue(agent_id, to);
break;
case et_room2elevator:
//到达电梯,插入电梯等候队列
enqueue(agent_id, from / 100 * 100);
break;
case et_in_room:
//出房间,去电梯或去下一房间或exit
room[from / 100][from % 100].o = false;
if (to == -1) {
//即将exit
if (from / 100 == 1) {
Schedule * s = new Schedule;
s->e = et_exit;
s->start_time = current_time;
s->end_time = current_time + event_time[et_exit];
s->from = -1;
s->to = -1;
agent[agent_id].push_schedule(s);
} else {
//即将下电梯然后exit
Schedule * s = new Schedule;
s->e = et_room2elevator;
s->start_time = current_time;
s->end_time = current_time + event_time[et_room2elevator];
s->from = from;
s->to = -1;
agent[agent_id].push_schedule(s);
}
} else if (floor == from / 100) {
//下一房间在同一楼,room2room
Schedule * s = new Schedule;
s->e = et_room2room;
s->start_time = current_time;
s->end_time = current_time + event_time[et_room2room];
s->from = from;
s->to = to;
agent[agent_id].push_schedule(s);
} else {
//下一房间在不同楼,room2elevator
Schedule * s = new Schedule;
s->e = et_room2elevator;
s->start_time = current_time;
s->end_time = current_time + event_time[et_room2elevator];
s->from = from;
s->to = to;
agent[agent_id].push_schedule(s);
}
break;
case et_in_elevator:
//出电梯,去下一房间或exit
if (to == -1) {
//exit
Schedule * s = new Schedule;
s->e = et_exit;
s->start_time = current_time;
s->end_time = current_time + event_time[et_exit];
agent[agent_id].push_schedule(s);
} else {
//去房间
Schedule * s = new Schedule;
s->e = et_elevator2room;
s->start_time = current_time;
s->end_time = current_time + event_time[et_room2room];
s->from = from;
s->to = to;
agent[agent_id].push_schedule(s);
}
break;
case et_exit:
//该agent所有plan和schedule已完成
agent[agent_id].exit_time = s->end_time;
break;
}
}
int str2int(string time) {
return ((time[0] - '0') * 10 + (time[1] - '0')) * 3600 +
((time[3] - '0') * 10 + (time[4] - '0')) * 60 +
(time[6] - '0') * 10 + (time[7] - '0');
}
string int2str(int time) {
string str;
str += time / 3600 / 10 + '0';
str += time / 3600 % 10 + '0';
str += ":";
time = time - time / 3600 * 3600;
str += time / 60 / 10 + '0';
str += time / 60 % 10 + '0';
str += ":";
time = time - time / 60 * 60;
str += time / 10 + '0';
str += time % 10 + '0';
return str;
}
void input() {
while (true) {
char prio;
cin >> prio;
if (prio == '.') {
break;
}
int agent_id = prio - 'A';
agent[agent_id].e = true;
string entry;
cin >> entry;
int entry_time = str2int(entry);
agent[agent_id].entry_time = entry_time;
//读入计划
while (true) {
int room_id;
cin >> room_id;
if (room_id == 0) {
break;
}
int time;
cin >> time;
agent[agent_id].push_plan(make_pair(room_id, time));
}
//将entry event写入schedule
Schedule * schedule = new Schedule;
schedule->e = et_entry;
schedule->start_time = entry_time;
schedule->end_time = entry_time + event_time[et_entry];
schedule->from = 0;
schedule->to = agent[agent_id].popr_plan().first;
schedule->next = NULL;
agent[agent_id].push_schedule(schedule);
}
}
void initialize() {
for (int i = 0; i < 26; ++i) {
agent[i].e = false;
agent[i].id = i;
agent[i].entry_time = -1;
agent[i].exit_time = 86401;
agent[i].plan = NULL;
agent[i].schedule = NULL;
}
for (int i = 0; i < 11; ++i) {
for (int j = 0; j < 11; ++j) {
room[i][j].waiting_cnt = 0;
for (int k = 0; k < 26; ++k) {
room[i][j].o = false;
room[i][j].free_time = 0;
room[i][j].waiting_queue[k] = false;
}
}
}
}
void print_entry(int start, int end) {
cout << int2str(start) << " " << int2str(end) << " Entry" << endl;
}
void print_exit(int start, int end) {
cout << int2str(start) << " " << int2str(end) << " Exit" << endl;
}
void print_in_room(int start, int end, int room) {
cout << int2str(start) << " " << int2str(end) << " Stay in room "
<< setfill('0') << setw(4) << room << endl;
}
void print_in_elevator(int start, int end) {
cout << int2str(start) << " " << int2str(end) << " Stay in elevator" << endl;
}
void print_room2room(int start, int end, int from, int to) {
cout << int2str(start) << " " << int2str(end) << " Transfer from room "
<< setfill('0') << setw(4) << from << " to room " << setfill('0') << setw(4) << to << endl;
}
void print_elevator2room(int start, int end, int room) {
cout << int2str(start) << " " << int2str(end) << " Transfer from elevator to room "
<< setfill('0') << setw(4) << room << endl;
}
void print_room2elevator(int start, int end, int room) {
cout << int2str(start) << " " << int2str(end) << " Transfer from room "
<< setfill('0') << setw(4) << room << " to elevator" << endl;
}
void print_wait_room(int start, int end, int room) {
if (start == end) return;
cout << int2str(start) << " " << int2str(end) << " Waiting in front of room "
<< setfill('0') << setw(4) << room << endl;
}
void print_wait_elevator(int start, int end) {
if (start == end) return;
cout << int2str(start) << " " << int2str(end) << " Waiting in elevator queue" << endl;
}
void output() {
for (int i = 0; i < 26; ++i) {
if (agent[i].e == false) {
continue;
}
cout << char('A' + i) << endl;
Schedule * schedule = agent[i].schedule;
while (schedule != NULL) {
switch (schedule->e) {
case et_entry: print_entry(schedule->start_time, schedule->end_time); break;
case et_wait_elevator: print_wait_elevator(schedule->start_time, schedule->end_time); break;
case et_wait_room: print_wait_room(schedule->start_time, schedule->end_time, schedule->from); break;
case et_room2room: print_room2room(schedule->start_time, schedule->end_time, schedule->from, schedule->to); break;
case et_elevator2room: print_elevator2room(schedule->start_time, schedule->end_time, schedule->to); break;
case et_room2elevator: print_room2elevator(schedule->start_time, schedule->end_time, schedule->from);break;
case et_in_room: print_in_room(schedule->start_time, schedule->end_time, schedule->from); break;
case et_in_elevator: print_in_elevator(schedule->start_time, schedule->end_time); break;
case et_exit: print_exit(schedule->start_time, schedule->end_time); break;
}
schedule = schedule->next;
}
cout << endl;
}
}
int main() {
initialize();
input();
for (current_time = 0; current_time < 24 * 3600; ++current_time) {
//处理每个客户的schedule
for (int agent_id = 0; agent_id < 26; ++agent_id) {
//没有该客户
if (agent[agent_id].e == false) continue;
//该客户该时刻还未到达
if (current_time < agent[agent_id].entry_time + event_time[et_entry]) continue;
//该客户该时刻已经离开
if (current_time > agent[agent_id].exit_time) continue;
Schedule * s = agent[agent_id].popr_schedule();
//该顾客上一schedule还未完成
if (current_time < s->end_time) continue;
//该顾客上一schedule恰好完成,准备下一schedule
if (current_time == s->end_time) {
process(agent_id);
}
}
//处理每个房间和电梯的等待队列
for (int floor = 1; floor < 11; ++floor) {
for (int id = 0; id < 11; ++id) {
//电梯5秒一趟
if (id == 0) {
if (current_time % 5 != 0) {
//所有队列继续等待
for (int k = 0; k < 26; ++k) {
if (room[floor][id].waiting_queue[k] == true) {
agent[k].popr_schedule()->end_time = current_time + 5 - current_time % 5 ;
}
}
} else {
//电梯来了!
room[floor][id].o = false;
if (!room[floor][id].waiting_q_empty()) {
//队列中的第一个进入电梯
int agent_id = room[floor][id].pop();
room[floor][id].o = true;
room[floor][id].free_time = current_time + 5;
Schedule * s = new Schedule;
s->e = et_in_elevator;
s->start_time= current_time;
int des = agent[agent_id].popr_schedule()->to;
if (des == -1) {
s->end_time = current_time + (floor - 1) * event_time[et_in_elevator];
} else {
s->end_time = current_time + abs(agent[agent_id].popr_schedule()->to / 100 - floor) * event_time[et_in_elevator];
}
s->from = floor * 100 + id;
s->to = agent[agent_id].popr_schedule()->to;
agent[agent_id].push_schedule(s);
//其余继续等候
for (int i = 0; i < 26; ++i) {
if (room[floor][id].waiting_queue[i] == true) {
agent[i].popr_schedule()->end_time = current_time + 5;
}
}
}
}
} else {
//是房间
if (room[floor][id].o == true) continue; //该房间当前有人
if (!room[floor][id].waiting_q_empty()) {
//队列第一人进入房间
int first_agent = room[floor][id].pop();
int duration = agent[first_agent].pop_plan().second;
Schedule * s = new Schedule;
s->e = et_in_room;
s->start_time = current_time;
s->end_time = current_time + duration;
s->from = floor * 100 + id;
if (agent[first_agent].plan != NULL) {
s->to = agent[first_agent].popr_plan().first;
} else {
s->to = -1;
}
agent[first_agent].push_schedule(s);
room[floor][id].o = true;
room[floor][id].free_time = current_time + duration;
//其余继续等候
for (int i = 0; i < 26; ++i) {
if (room[floor][id].waiting_queue[i] == true) {
agent[i].popr_schedule()->end_time = room[floor][id].free_time;
}
}
}
}
}
}
}
output();
system("pause");
return 0;
}