又一道悲剧的题目……不过这次的悲剧更多的是POJ的悲剧……
题目意思其实不太复杂,赤裸裸的模拟题,非常烦的模拟……据说做的时候会有人看直播围观……
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<br></br>0101 100<br></br>0110 50<br></br>0202 90<br></br>0205 50<br></br>0<br></br>B 10:01:00<br></br>0105 100<br></br>0201 5<br></br>0205 200<br></br>0<br></br>.<br></br>
Sample Output
A<br></br>10:00:00 10:00:30 Entry<br></br>10:00:30 10:02:10 Stay in room 0101<br></br>10:02:10 10:02:20 Transfer from room 0101 to room 0110<br></br>10:02:20 10:03:10 Stay in room 0110<br></br>10:03:10 10:03:20 Transfer from room 0110 to elevator<br></br>10:03:20 10:03:50 Stay in elevator<br></br>10:03:50 10:04:00 Transfer from elevator to room 0202<br></br>10:04:00 10:05:30 Stay in room 0202<br></br>10:05:30 10:05:40 Transfer from room 0202 to room 0205<br></br>10:05:40 10:07:40 Waiting in front of room 0205<br></br>10:07:40 10:08:30 Stay in room 0205<br></br>10:08:30 10:08:40 Transfer from room 0205 to elevator<br></br>10:08:40 10:09:10 Stay in elevator<br></br>10:09:10 10:09:40 Exit<br></br><br></br>B<br></br>10:01:00 10:01:30 Entry<br></br>10:01:30 10:03:10 Stay in room 0105<br></br>10:03:10 10:03:20 Transfer from room 0105 to elevator<br></br>10:03:20 10:03:25 Waiting in elevator queue<br></br>10:03:25 10:03:55 Stay in elevator<br></br>10:03:55 10:04:05 Transfer from elevator to room 0201<br></br>10:04:05 10:04:10 Stay in room 0201<br></br>10:04:10 10:04:20 Transfer from room 0201 to room 0205<br></br>10:04:20 10:07:40 Stay in room 0205<br></br>10:07:40 10:07:50 Transfer from room 0205 to elevator<br></br>10:07:50 10:08:20 Stay in elevator<br></br>10:08:20 10:08:50 Exit<br></br>
做的时候用到了链表,然后运行结果是Runtime error…于是找可能超界或者其他啥导致Runtime error的地方,找到了一些没注意到的可能产生错误的地方,比如一个地方合并Waiting状态的时候没有考虑node->next是NULL的情况,不过改了还是继续Runtime error。找到原题的测试数据,基本上对的上,最后一点点明显是原题的结果有问题,排除了程序错误。最后没办法,就一点点注释掉代码来找错误的地方……(我可怜的通过率。。。。。。)最后发现竟然是在遍历链表的时候出错……看了一遍又一遍我的链表程序,确认没有出错……最后没办法,把动态申请链表空间改成一次性开了一个20W的数组,尽然就AC了……通过的时候内存只1500多K,离超内存还很远……POJ的BUG了……悲剧的……
说一下这道题目吧,关于电梯容易理解错,其实题目的意思是没5秒钟没层楼都有一部电梯,这部电梯既可以向上,也可以向下……然后各层楼电梯不会相撞以及其他更加诡异的……
具体做的时候我没有创建排队这么个东西,而是记录每个人当前的时间以及所处状态,然后循环找到时间最靠前的人,应为编号小的人优先级高,这样子很方便的处理了排队问题。然后通过当前状态推得下一步状态,继续刷时间啥的……悲剧,说不清楚……贴代码……写了300行不到点,有些东西有点多余,重写的话估计能够200行左右写完。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a, b) ((a)>(b)?(a):(b))
enum ActiveType{Waiting, Going, Staying};
typedef struct Active{
ActiveType activeType;
int PlaceStart;//前两位表示层数,后一位0表示刚刚到这层,1到10表示10个房间,
int PlaceEnd; //11表示上楼或下楼的电梯,0112表示下到底层电梯,0113表示已经出楼
int TimeStart;
int TimeOver;
Active *Next;
}Active;
int toView[35][100][100];
int enterTime[35];
Active Actives[35];
Active *Status[35];//当前状态
int now;
int roomFree[15][100];
Active aaaaa[200000];
int bbbbb;
void printRoom(int room)
{
if(room%100 == 0 || room%100 == 11 || room%100 == 12)
printf("elevator");
else{
char tmp[100];
sprintf(tmp, "%2d%2d", room/100, room%100);
for(int i=0; i<10; i++)
if(tmp[i] == ' ')
tmp[i] = '0';
printf("room %s", tmp);
}
}
void printTime(int time)
{
char tmp[100];
sprintf(tmp, "%2d:%2d:%2d", time/3600, time/60%60, time%60);
int i;
for(i=0; i<8; i++)
if(tmp[i] == ' ')
tmp[i] = '0';
printf("%s ", tmp);
}
void printnode(Active *active)
{
if(active->PlaceEnd == 100 || active->TimeOver == 100000000)
return;
else{
printTime(active->TimeStart);
printTime(active->TimeOver);
}
if(active->PlaceStart == 100){
printf("Entry\n");
}
else if(active->PlaceEnd == 113){
printf("Exit\n");
}
else if(active->PlaceEnd % 100 == 0){
printf("Stay in elevator\n");
}
else if(active->activeType == Waiting){
if(active->PlaceEnd % 100 == 11)
printf("Waiting in elevator queue\n");
else{
printf("Waiting in front of ");
printRoom(active->PlaceEnd);
printf("\n");
}
}
else if(active->activeType == Going){
printf("Transfer from ");
printRoom(active->PlaceStart);
printf(" to ");
printRoom(active->PlaceEnd);
printf("\n");
}
else if (active->activeType == Staying){
printf("Stay in ");
printRoom(active->PlaceEnd);
printf("\n");
}
}
void print(int code)
{
Active *tmp;
tmp = &Actives[code];
printf("%c\n", 'A'+code);
while(tmp!= NULL) {
if (tmp->Next != NULL) {
if (tmp->activeType == Waiting && tmp->Next->activeType == Waiting)
&nbs;
p; tmp->Next->TimeStart = tmp->TimeStart;
else
printnode(tmp);
} else
printnode(tmp);
tmp = tmp->Next;
}
printf("\n");
}
int Time2Int(char time[])
{
int a, b, c;
sscanf(time, "%d:%d:%d", &a, &b, &c);
return (a*60+b)*60+c;
}
int InitList(char code)
{
int a, b;
char s[100];
scanf("%s", s);
if(code < 'A' || code > 'Z')
exit(0);
enterTime[code-'A'] = Time2Int(s);
while(1){
scanf("%d", &a);
if(a == 0)
return 0;
scanf("%d", &b);
toView[code-'A'][a/100][a%100] = b;
}
return 0;
}
int GetNextActive(int code, int *timeEnd, ActiveType *active, int *PlaceStart, int *PlaceEnd)
{
int i, j, k, tt;
tt=Status[code]->activeType;
k = Status[code]->PlaceEnd;
if(k / 100 > 10 || k / 100 < 0 || k % 100 > 13 || k % 100 < 0)
exit(0);
if(code > 26 || code < 0)
exit(0);
roomFree[k/100][11] = (max(roomFree[k/100][11], now)-1)/5*5+5;
if (tt == Staying) {//刚刚从某个房间或者电梯出来
i = k / 100;
j = k % 100;
if (i == 0)
i ++;
if(k == 112){//准备出楼
*timeEnd = now+30;
*active = Going;
*PlaceStart = k;
*PlaceEnd = 113;
return 0;
}
for (; j <= 10; j++)
if (toView[code][i][j] > 0) {//本层还有房间要参观,走到那个房间
if(k != 100)
*timeEnd = now+10;
else
*timeEnd = now+30;
*active = Going;
*PlaceStart = k;
*PlaceEnd = i*100+j;
return 0;
}
for(i=i+1; i<=10; i++)
for(j=1; j<=10; j++)
if(toView[code][i][j] > 0){//上层有房间要参观,走到电梯
if (k != 100)
*timeEnd = now+10;
else
*timeEnd = now+30;
*active = Going;
*PlaceStart = k;
if (k != 0)
*PlaceEnd = k/100*100+11;
else
*PlaceEnd = 100+11;
return 0;
}
//无房间参观,出楼
if (k / 100 == 1) {//在一楼
*timeEnd = now + 30;
*active = Going;
*PlaceStart = k;
*PlaceEnd = 113;
return 0;
} else {//去电梯下1楼
*timeEnd = now+10;
*active = Going;
*PlaceStart = k;
*PlaceEnd = k/100*100+11;
return 0;
}
}
else if (tt == Waiting || tt == Going){//正在某个房间或者电梯等待以及走向某个房间或者电梯
if (k == 113) {//已经出楼
*timeEnd = 100000000;
*active = Staying;
&
nbsp; *PlaceStart = *PlaceEnd = 113;
return 0;
}
if(roomFree[k/100][k%100] > now){//继续等待
*active = Waiting;
*timeEnd = roomFree[k/100][k%100];
*PlaceStart = *PlaceEnd = k;
return 0;
}
else {
*active = Staying;
if (k % 100 == 11) {//进电梯
roomFree[k / 100][k % 100] = now + 5;
for (i = k / 100 + 1; i <= 10; i++){
for (j = 1; j <= 10; j++)
if (toView[code][i][j] > 0) {//上楼
*timeEnd = now + (i - k / 100)*30;
*active = Staying;
*PlaceStart = k;
*PlaceEnd = i * 100;
roomFree[k/100][k%100] = now+5;
return 0;
}
}
*timeEnd = now + (k / 100 - 1)*30;
*active = Staying;
*PlaceStart = k;
*PlaceEnd = 112;
roomFree[k/100][k%100] = now+5;
return 0;
} else {//进房间
*timeEnd = now + toView[code][k / 100][k % 100];
*active = Staying;
*PlaceStart = *PlaceEnd = k;
toView[code][k / 100][k % 100] = 0;
roomFree[k / 100][k%100] = *timeEnd;
return 0;
}
}
}
return 0;
}
int main()
{
bbbbb=0;
char s[100];
int i, k;
memset(toView, 0, sizeof(toView));
memset(enterTime, 0, sizeof(enterTime));
memset(Actives, 0, sizeof(Actives));
memset(roomFree, 0, sizeof(roomFree));
while(1){
scanf("%s", s);
if(s[0] == '.')
break;
InitList(s[0]);
}
for(i=0; i<30; i++)
if(enterTime[i] > 0){
Actives[i].PlaceStart = Actives[i].PlaceEnd= 100;
Actives[i].Next = NULL;
Actives[i].TimeStart = Actives[i].TimeOver = enterTime[i];
Actives[i].activeType = Staying;
Status[i] = &Actives[i];
}
else{
Actives[i].TimeOver = 100000000;
Actives[i].Next = NULL;
Status[i] = &Actives[i];
}
Status[29]->TimeOver = 100000000;
while(1){
k = 29;
for(i=0; i<26; i++)
if(Status[i]->TimeOver < Status[k]->TimeOver)
k = i;
if (Status[k]->TimeOver == 100000000)
break;
now = Status[k]->TimeOver;
//Active *tmp = &aaaaa[bbbbb++];
Active *tmp = new Active;
if(bbbbb >= 200000)
exit(0);
tmp->TimeStart = Status[k]->TimeOver;
GetNextActive(k, &tmp->TimeOver, &tmp->activeType, &tmp->PlaceStart, &tmp->PlaceEnd);
tmp->Next == NULL;
Status[k]->Next = tmp;
Status[k] = tmp;
}
for(i=0; i<26; i++)
&nbs;
p; if(enterTime[i]> 0)
print(i);
return 0;
}