企业官网建设流程全解析

题目描述

在一个火车站，只有一个发车通道。有两种列车：快车（Express\texttt{Express}Express）和普通车（Ordinary\texttt{Ordinary}Ordinary）。普通车必须等到所有快车发车完毕后才能发车，但若普通车正在发车，新到的快车必须等待该普通车离开后才能使用通道。快车和普通车的发车时间（从开始启动到完全离开）分别为LeL_eLe​和LoL_oLo​。两列快车到达的时间间隔为AeA_eAe​，两列普通车到达的时间间隔为AoA_oAo​。总观察时间为TTT。

初始时发车通道为空，第一辆到达的列车必为快车。要求输出任意时刻等待发车的列车数量（快车数、普通车数），并计算快车、普通车和所有列车的平均等待时间（采用整数除法），以及每列车的实际等待时间（截断至观察时刻TTT）。

输入格式

输入包含多行，每行有五个整数，分别代表Ae,Ao,Le,Lo,TA_e, A_o, L_e, L_o, TAe​,Ao​,Le​,Lo​,T。最后一行是五个0，该行不处理。

输出格式

对于每组输入，输出分为三个部分：

1. 等待队列状态数组：每行三个整数，依次为时刻、等待快车数、等待普通车数。仅当等待数量发生变化时输出该三元组，且时刻不超过TTT。数组末尾单独输出一个数字0。
2. 平均等待时间：一行三个整数，分别为We,Wo,WtW_e, W_o, W_tWe​,Wo​,Wt​（整数除法），后跟一行数字0。
3. 每列车等待时间数组：每行两个元素，列车标识和等待时间。快车标识为E后接编号（按到达顺序），普通车为O后接编号。等待时间为实际等待时间截断至TTT（即若列车在TTT后发车，则等待时间记为T−到达时刻T - \text{到达时刻}T−到达时刻）。该部分末尾不输出额外的0。

每组输出之间用一个空行分隔（第一组前无空行，最后一组后无多余空行）。

样例

输入

3 6 6 2 30 6 7 7 5 8 0 0 0 0 0

输出

0 0 0 3 1 0 6 1 1 9 2 1 12 2 2 15 3 2 18 3 3 21 4 3 24 4 4 27 5 4 30 5 5 0 6 12 8 0 E1 0 E2 3 E3 6 E4 9 E5 12 E6 15 E7 12 E8 9 E9 6 E10 3 E11 0 O1 24 O2 18 O3 12 O4 6 O5 0 0 0 0 6 1 0 7 0 1 0 0 1 0 0 E1 0 E2 1 O1 1

题目分析

本题是一个单服务台、两类顾客（快车与普通车）的排队系统，但规则特殊：

• 快车具有绝对优先权，但普通车一旦开始服务，不可被抢占。
• 到达过程是确定性的（等间隔到达），服务时间也是确定的。
• 观察窗口TTT只影响输出三元组和等待时间的截断，但所有到达列车（到达时间≤T\le T≤T）均需在模拟中完成服务，以便计算完整的等待时间。

直接按时间步进模拟会因时间间隔大而低效，因此采用事件驱动模拟。主要事件包括列车到达、列车完成服务、服务开始。事件序列中，同一时刻需按“完成 → 到达 → 尝试开始服务”的顺序处理，以保证语义正确。

等待时间的计算需注意：若列车在时刻ttt开始服务，其实际等待时间为t−arrivet - \textit{arrive}t−arrive，但若t>Tt > Tt>T，则截断为T−arriveT - \textit{arrive}T−arrive（因为题目只统计观察窗口内的等待时间）。平均等待时间采用整数除法（向下取整）。

输出格式要求记录三元组仅在状态变化时输出，且初始状态(0, 0, 0)必须包含。列车等待时间列表按编号顺序输出（编号按到达顺序分配，同一时刻快车优先编号）。

解题思路

1. 生成到达事件

分别生成快车和普通车的到达时刻。快车第一辆在时刻000到达，之后每隔AeA_eAe​到达一辆，直到超过TTT为止。普通车第一辆在时刻AoA_oAo​到达（因为题目明确第一辆是快车），之后每隔AoA_oAo​到达一辆。将所有到达事件存入数组，按时间排序；同一时刻快车事件排在普通车事件之前，以保证编号顺序与到达顺序一致。

2. 事件驱动模拟

维护两个队列：快车等待队列eq和普通车等待队列oq，队列中存储列车在全局数组trains中的索引。同时维护当前等待数量waitE、waitO，以及上一次记录的状态lastE、lastO。

模拟循环的条件为：还有未处理的到达事件，或服务台忙，或任一队列非空。每次迭代计算下一个事件的时间：

• 下一个到达时间nextArrival（若有）；
• 当前服务完成时间nextFinish（若忙）；
• 取两者较小值作为当前时刻cur。

随后按顺序执行：

1. 处理完成事件：若finishTime == cur，将服务台置为空闲。
2. 处理所有到达事件：将所有到达时刻为cur的列车加入对应的等待队列，更新waitE/waitO。
3. 尝试开始新服务：若服务台空闲，优先从快车队列取车；若快车队列为空，则从普通车队列取车。取出时，计算该列车的等待时间（截断至TTT），并记录到等待时间列表中；然后设置服务台为忙，预计完成时间为cur + Le（快车）或cur + Lo（普通车）。
4. 记录状态：若cur <= T且等待数量与上次记录不同，则将三元组(cur, waitE, waitO)存入结果数组。

初始时刻，强制将(0, 0, 0)加入三元组数组，以保证初始状态被输出。

3. 计算平均等待时间

遍历记录的每列车等待时间列表，分别累加快车、普通车和所有列车的等待时间，除以对应的列车数量，使用整数除法（即long long累加后取整）。注意：只有实际到达且被服务的列车才计入统计。

4. 输出

• 第一部分：按顺序输出所有三元组，每行一个，末尾打印数字0。
• 第二部分：输出三个平均等待时间，末尾打印数字0。
• 第三部分：按编号升序依次输出快车和普通车的等待时间，编号顺序即为列车在trains中的出现顺序（因为到达事件已排序），末尾不打印额外的0。

每组输出间插入一个空行，第一组前无空行。

代码实现

// The Problem of Train Setout// UVa ID: 528// Verdict: Accepted// Submission Date: 2026-06-27// UVa Run Time: 0.040s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structArrival{inttime;inttype;// 0: 快车, 1: 普通车};structTrain{inttype;intid;intarrive;intwait;// 截断后的等待时间};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intAe,Ao,Le,Lo,T;boolfirstCase=true;while(cin>>Ae>>Ao>>Le>>Lo>>T){if(Ae==0&&Ao==0&&Le==0&&Lo==0&&T==0)break;if(!firstCase)cout<<"\n";firstCase=false;// ---------- 生成到达事件 ----------vector<Arrival>arrivals;intt=0;while(t<=T){arrivals.push_back({t,0});if(Ae==0)break;t+=Ae;}t=Ao;while(t<=T){arrivals.push_back({t,1});if(Ao==0)break;t+=Ao;}sort(arrivals.begin(),arrivals.end(),[](constArrival&a,constArrival&b){if(a.time!=b.time)returna.time<b.time;returna.type<b.type;// 同时间快车优先（编号顺序）});// ---------- 模拟 ----------vector<Train>trains;queue<int>eq,oq;intwaitE=0,waitO=0;intlastE=-1,lastO=-1;vector<tuple<int,int,int>>triplets;autorecord=[&](intcurTime){if(waitE!=lastE||waitO!=lastO){triplets.push_back({curTime,waitE,waitO});lastE=waitE;lastO=waitO;}};// 强制记录初始状态 (0,0,0)triplets.push_back({0,0,0});lastE=0;lastO=0;boolbusy=false;intfinishTime=0;intidx=0;intcur=0;inteid=0,oid=0;vector<int>waitEList,waitOList;while(idx<(int)arrivals.size()||busy||!eq.empty()||!oq.empty()){intnextArrival=(idx<(int)arrivals.size())?arrivals[idx].time:INT_MAX;intnextFinish=busy?finishTime:INT_MAX;intnextTime=min(nextArrival,nextFinish);if(nextTime==INT_MAX)break;cur=nextTime;// 1. 处理完成事件if(busy&&finishTime==cur){busy=false;}// 2. 处理所有到达事件while(idx<(int)arrivals.size()&&arrivals[idx].time==cur){inttype=arrivals[idx].type;Train tr;tr.type=type;tr.id=(type==0)?++eid:++oid;tr.arrive=cur;tr.wait=-1;trains.push_back(tr);inttidx=(int)trains.size()-1;if(type==0){eq.push(tidx);++waitE;}else{oq.push(tidx);++waitO;}++idx;}// 3. 尝试开始新服务if(!busy){if(!eq.empty()){inttidx=eq.front();eq.pop();--waitE;Train&tr=trains[tidx];intactualWait=cur-tr.arrive;tr.wait=min(actualWait,T-tr.arrive);// 截断到TwaitEList.push_back(tr.wait);busy=true;finishTime=cur+Le;}elseif(!oq.empty()){inttidx=oq.front();oq.pop();--waitO;Train&tr=trains[tidx];intactualWait=cur-tr.arrive;tr.wait=min(actualWait,T-tr.arrive);waitOList.push_back(tr.wait);busy=true;finishTime=cur+Lo;}}// 4. 记录状态（仅当 cur <= T）if(cur<=T)record(cur);}// ---------- 输出第一部分 ----------for(auto&tp:triplets)cout<<get<0>(tp)<<" "<<get<1>(tp)<<" "<<get<2>(tp)<<"\n";cout<<"0\n";// ---------- 计算平均值（整数除法） ----------intWe=0,Wo=0,Wt=0;intcntE=(int)waitEList.size();intcntO=(int)waitOList.size();if(cntE>0){longlongsumE=0;for(intw:waitEList)sumE+=w;We=(int)(sumE/cntE);}if(cntO>0){longlongsumO=0;for(intw:waitOList)sumO+=w;Wo=(int)(sumO/cntO);}if(cntE+cntO>0){longlongsumAll=0;for(intw:waitEList)sumAll+=w;for(intw:waitOList)sumAll+=w;Wt=(int)(sumAll/(cntE+cntO));}cout<<We<<" "<<Wo<<" "<<Wt<<"\n";cout<<"0\n";// ---------- 输出第三部分 ----------for(auto&tr:trains){if(tr.type==0&&tr.wait>=0)cout<<"E"<<tr.id<<" "<<tr.wait<<"\n";}for(auto&tr:trains){if(tr.type==1&&tr.wait>=0)cout<<"O"<<tr.id<<" "<<tr.wait<<"\n";}// 第三部分末尾不输出 0}return0;}

总结

本题是典型的离散事件模拟，关键技巧在于：

• 事件驱动思想：避免按时间步长循环，只处理事件发生的时刻，提高效率。
• 优先级与不可抢占：快车队列优先，但普通车正在服务时不可打断，因此在服务开始前判断队列优先级，而非在服务过程中。
• 等待时间的截断：注意题目仅要求观察窗口内的等待时间，截断操作需正确实现。
• 输出格式细节：初始状态必须输出，状态变化时记录，每组输出间的空行处理，以及末尾数字0的位置（第三部分无末尾0）均需严格遵守。

掌握这些模拟和输出细节，即可正确解决此类排队系统问题。