首页 > 代码库 > POJ1025 Department
POJ1025 Department
POJ1025
是一道模拟题。
这题第一个障碍是现在少见的循环电梯 （‘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<E, vector<E> > que,为此还需定义小于(<)运算符
bool operator < (const E& a, const E& b){ ...}
4.维护vector<S> record[26]：特工的行动序列
5.房间状态的维护
（1）room[11][11] ：房间空闲的起始时刻，初始化为0，模拟过程中要不断更新
（2）updated[11][11]: updated[i][j]表示room[i][j]是否更新过
若当前等待事件的目标房间（或电梯）更新过，则要将当前等待事件再次入队
6.处理过程中时间统一化成秒，输出时再转化成指定的格式
7.其他细节见代码
网上见到的题解大多代码过长，可读性差，我自己写了个比较简明的版本，200行多一点
#include<cstdio>#include<algorithm>#include<vector>#include<queue>using namespace std;typedef pair<int,int> P;int room[11][11]; //room[i][j]:房间空闲的起始时刻bool updated[11][11]; //起始时刻是否已更新vector<P> agent[26];int time[26], sta[26];int done[26];//已经访问的房间数目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/100, r=a.pos%100; //等电梯 if(a.pos%100==0) { int t1=(a.beg%5?(a.beg/5+1)*5:a.beg); int t2=(b.beg%5?(b.beg/5+1)*5: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<E, vector<E> >que; //排队vector<S> record[26]; //行程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]=3600*h+60*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, 0)); //! Exit }}void init(){ for(int i=0; i<26; i++) { if(!agent[i].size()) continue; if(agent[i][0].first/100==1) record[i].push_back(S(agent[i][0].first,30));//往一层某房间 else record[i].push_back(S(100,30));//往一层电梯 time[i]+=30; 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/100; r=e.pos%100; if(updated[f][r]) { que.push(e); updated[f][r]=false; continue; } if(r==0) //等电梯 { if(e.beg<=room[f][r]) wait=room[f][r]-e.beg; else wait=(e.beg%5? 5-e.beg%5: 0); if(wait) record[id].push_back(S(e.pos, wait)); time[id]+=wait; room[f][r]=time[id]+5; updated[f][r]=true; to=agent[id][done[id]].first; if(to==0) //!Exit { cost=30*(e.pos/100-1); record[id].push_back(S(100, cost)); record[id].push_back(S(to,30)); continue; } cost=30*(max(to/100,e.pos/100)-min(to/100,e.pos/100)); record[id].push_back(S(to/100*100, cost)); //在电梯里 time[id]+=cost; record[id].push_back(S(to, 10)); //往房间 time[id]+=10; que.push(E(id,time[id],to)); } else //等房间 { wait=max(room[f][r]-e.beg,0); 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==0&&f==1) //!Exit { record[id].push_back(S(to, 30)); continue; } if(to/100!=f) to=f*100; //需等电梯 record[id].push_back(S(to, 10)); //往电梯 time[id]+=10; que.push(E(id,time[id],to)); } }}void t_p(int t){ int h=t/3600, m=(t%3600)/60, s=t%3600%60; printf("%02d:%02d:%02d ",h,m,s);}void e_p(int pre, int cur){ if(pre==0) {printf("Entry\n"); return;} if(cur==0) {printf("Exit\n"); return;} if(cur<0) {printf("Stay in room %04d\n",-cur); return;} if(pre==cur) { if(cur%100==0) printf("Waiting in elevator queue\n"); else printf("Waiting in front of room %04d\n",cur); return; } if(pre%100==0&&cur%100==0) {printf("Stay in elevator\n"); return;}; if(pre<0) { if(cur%100==0) 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=0; i<26; i++) { if(!record[i].size()) continue; t=sta[i]; pre_pos=0; printf("%c\n",‘A‘+i); for(int j=0; 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 0;}
POJ1025 Department
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。