POJ #1025 Department
模拟题。
这题第一个障碍是现在少见的循环电梯 （'pater-noster' elevator)
"The building has `pater-noster' elevator, i.e. elevator build up from several cabins running all around."
这种叫做 paster-noster 的电梯是 running all around 的，如动画所示，题目中费解的地方便清楚了。（欲知详情，请往维基百科）
第二个难点：模拟
模拟的核心是排队——等电梯或等房间
一开始可能感觉无从下手，模拟题的分析方法最主要的是分析事件。
准确地说，这道题有且仅有两个事件
排队等候（wating in queue)
行动（progress)
题目要求输出的是特工的活动记录（record）
solution:
1.用结构体表示事件：排队等候E，行动S
2.将电梯也看做房间编号是XX00
3.用优先队列维护排队等候的序列priority_queue
bool operator < (const E& a, const E& b){ …}
4.维护vector record[26]：特工的行动序列
5.房间状态的维护
（1）room[11][11] ：房间空闲的起始时刻，初始化为0，模拟过程中要不断更新
（2）updated[11][11]: updated[i][j]表示room[i][j]是否更新过
若当前等待事件的目标房间（或电梯）更新过，则要将当前等待事件再次入队
6.处理过程中时间统一化成秒，输出时再转化成指定的格式
7.其他细节见代码
网上见到的题解大多代码过长，可读性差，我自己写了个比较简明的版本，200行多一点
#include
using namespace std;
typedef pair
int room[][]; //room[i][j]:房间空闲的起始时刻
bool updated[][]; //起始时刻是否已更新
vector
agent[];
int time[], sta[];
int done[];//已经访问的房间数目
struct S //行程
{
int des;
int cost;
S(int des, int cost):des(des), cost(cost){}
};
struct E //排队
{
int code;
int beg;
int pos;
E(int code, int beg, int pos):code(code), beg(beg), pos(pos){};
};
bool operator <(const E &a, const E &b)
{
//两人不是站在同一队列中等待
if(a.pos!=b.pos) return a.beg > b.beg;
//两人同时到达
if(a.beg==b.beg) return a.code > b.code;
int f=a.pos/, r=a.pos%;
//等电梯
if(a.pos%==)
{
int t1=(a.beg%?(a.beg/+)\*:a.beg);
int t2=(b.beg%?(b.beg/+)\*:b.beg);
//两人乘同一班电梯，资历高的先进
if((t1<=room\[f\]\[r\]&&t2<=room\[f\]\[r\])||t1==t2)
return a.code>b.code;
return t1>t2;
}
else //等房间
{
//两人都得等，资历高的先进
if(a.beg<=room\[f\]\[r\]&&b.beg<=room\[f\]\[r\]) return a.code>b.code; //!room\[f\]\[r\]更新会影响这种比较
//至少有一个人不用等，先到的先进
else return a.beg > b.beg;
} }
priority_queue
vector record[]; //行程
void input()
{
FILE* fp=stdin; //提交时改成stdin
char c;
int h, m, s, pos, dur;
while(fscanf(fp," %[A-Z] ",&c))
{
int idx=c-'A';
fscanf(fp,"%d:%d:%d",&h,&m,&s);
time[idx]=sta[idx]=*h+*m+s;
while(fscanf(fp,"%d",&pos),pos)
{
fscanf(fp,"%d",&dur);
agent\[idx\].push\_back(P(pos, dur));
}
agent\[idx\].push\_back(P(pos, )); //! Exit
} }
void init()
{
for(int i=; i<; i++)
{
if(!agent[i].size()) continue;
if(agent[i][].first/==)
record[i].push_back(S(agent[i][].first,));//往一层某房间
else record[i].push_back(S(,));//往一层电梯
time[i]+=;
que.push(E(i,time[i],record[i].back().des));
}
}
void simulator()
{
int wait, id, cost, to, f, r;
while(!que.empty())
{
E e=que.top();
que.pop();
id=e.code;
f=e.pos/;
r=e.pos%;
if(updated[f][r])
{
que.push(e);
updated[f][r]=false;
continue;
}
if(r==) //等电梯
{
if(e.beg<=room\[f\]\[r\]) wait=room\[f\]\[r\]-e.beg;
else wait=(e.beg%? -e.beg%: );
if(wait) record\[id\].push\_back(S(e.pos, wait));
time\[id\]+=wait;
room\[f\]\[r\]=time\[id\]+;
updated\[f\]\[r\]=true;
to=agent\[id\]\[done\[id\]\].first;
if(to==) //!Exit
{
cost=\*(e.pos/-);
record\[id\].push\_back(S(, cost));
record\[id\].push\_back(S(to,));
continue;
}
cost=\*(max(to/,e.pos/)-min(to/,e.pos/));
record\[id\].push\_back(S(to/\*, cost)); //在电梯里
time\[id\]+=cost;
record\[id\].push\_back(S(to, )); //往房间
time\[id\]+=;
que.push(E(id,time\[id\],to));
}
else //等房间
{
wait=max(room\[f\]\[r\]-e.beg,);
if(wait) record\[id\].push\_back(S(e.pos,wait));
time\[id\]+=wait;
cost=agent\[id\]\[done\[id\]\].second;
record\[id\].push\_back(S(-e.pos, cost)); //取反
time\[id\]+=cost;
room\[f\]\[r\]=time\[id\];
updated\[f\]\[r\]=true;
done\[id\]++;
to=agent\[id\]\[done\[id\]\].first;
if(to==&&f==) //!Exit
{
record\[id\].push\_back(S(to, ));
continue;
}
if(to/!=f) to=f\*; //需等电梯
record\[id\].push\_back(S(to, )); //往电梯
time\[id\]+=;
que.push(E(id,time\[id\],to));
}
} }
void t_p(int t)
{
int h=t/, m=(t%)/, s=t%%;
printf("%02d:%02d:%02d ",h,m,s);
}
void e_p(int pre, int cur)
{
if(pre==) {printf("Entry\n"); return;}
if(cur==) {printf("Exit\n"); return;}
if(cur<) {printf("Stay in room %04d\n",-cur); return;}
if(pre==cur)
{
if(cur%==) printf("Waiting in elevator queue\n");
else printf("Waiting in front of room %04d\n",cur);
return;
}
if(pre%==&&cur%==) {printf("Stay in elevator\n"); return;};
if(pre<)
{
if(cur%==) printf("Transfer from room %04d to elevator\n",-pre);
else printf("Transfer from room %04d to room %04d\n",-pre, cur);
return;
}
else printf("Transfer from elevator to room %04d\n",cur);
}
void output()
{
int pre_pos, cur_pos, t;
for(int i=; i<; i++)
{
if(!record[i].size()) continue;
t=sta[i];
pre_pos=;
printf("%c\\n",'A'+i);
for(int j=; j!=record\[i\].size(); j++)
{
t\_p(t);
t\_p(t+=record\[i\]\[j\].cost);
cur\_pos=record\[i\]\[j\].des;
e\_p(pre\_pos, cur\_pos);
pre\_pos=cur\_pos;
}
printf("\\n");
} }
int main()
{
input();
init();
simulator();
output();
return ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章