UVa 467 Synching Signals

题目描述题目要求计算一组交通信号灯在初始全部为绿灯后第一次再次全部变为绿灯且在此之前至少有一个信号灯变为黄灯的时间。每个信号灯的周期为TTT秒其中绿灯持续T−5T-5T−5秒黄灯持续555秒红灯持续TTT秒因此一个完整周期为2T2T2T秒包括绿灯、黄灯和红灯。初始时刻所有信号灯均为绿灯开始。需要找到最小的t0t 0t0以秒为单位使得在ttt时刻所有信号灯均为绿灯且存在某个信号灯在(0,t)(0, t)(0,t)区间内曾变为黄灯。若t3600t 3600t3600秒606060分钟则输出无法同步。输入格式输入包含多行每行若干个整数至少222个最多101010个表示每个信号灯的周期时间秒。每个周期在101010到909090秒之间。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个数据集输出一行若在360036003600秒内找到同步时间输出Set X synchs again at M minute(s) and S second(s) after all turning green.否则输出Set X is unable to synch after one hour.其中XXX为数据集编号从111开始M⌊t/60⌋M \lfloor t / 60 \rfloorM⌊t/60⌋St mod 60S t \bmod 60Stmod60。样例输入25 25 25 25 25 25 15 30 20 21 30 23 29 25 27 22 19 20输出Set 1 synchs again at 5 minute(s) and 0 second(s) after all turning green. Set 2 synchs again at 0 minute(s) and 50 second(s) after all turning green. Set 3 synchs again at 1 minute(s) and 0 second(s) after all turning green. Set 4 is unable to synch after one hour. Set 5 synchs again at 0 minute(s) and 40 second(s) after all turning green.题目分析本题的核心是模拟信号灯的状态变化并寻找所有灯同时为绿灯的最小时间点t0t 0t0且满足在(0,t)(0, t)(0,t)内至少有一个灯曾变为黄灯。信号灯状态模型每个信号灯的周期为TTT秒。在一个完整的2T2T2T秒周期中[0,T−5][0, T-5][0,T−5]绿灯[T−5,T)[T-5, T)[T−5,T)黄灯[T,2T)[T, 2T)[T,2T)红灯[2T,3T−5][2T, 3T-5][2T,3T−5]绿灯下一个周期更一般地在时间ttt秒灯的状态由t mod (2T)t \bmod (2T)tmod(2T)决定若rT−5r T-5rT−5绿灯若T−5≤rTT-5 \le r TT−5≤rT黄灯若r≥Tr \ge Tr≥T红灯初始时刻t0t0t0所有灯均为绿灯r0r0r0。同步条件寻找最小的t0t 0t0使得对每个灯iiit mod (2Ti)Ti−5t \bmod (2T_i) T_i - 5tmod(2Ti​)Ti​−5绿灯条件且存在某个灯jjj使得在(0,t)(0, t)(0,t)区间内曾满足t′ mod (2Tj)≥Tj−5t \bmod (2T_j) \ge T_j - 5t′mod(2Tj​)≥Tj​−5且t′ mod (2Tj)Tjt \bmod (2T_j) T_jt′mod(2Tj​)Tj​黄灯条件。搜索方法由于时间上限为360036003600秒可以直接枚举ttt从111到360036003600检查每个ttt是否满足所有灯为绿灯。同时需要记录是否存在黄灯事件。但更高效的方法是使用优先队列模拟每个灯的下一次绿灯开始时间逐步推进时间。参考代码中使用了优先队列每个灯按2T2T2T的步长递增检查当前时间是否所有灯均为绿灯。若当前时间ttt满足条件且t0t 0t0则输出否则将ttt增加其步长继续。黄灯条件的判断由于初始时刻所有灯为绿灯第一个同步时间ttt必然大于000。只需检查ttt之前是否有黄灯发生。实际上由于初始状态是绿灯任何t0t 0t0都会经历至少一个灯的黄灯除非所有灯周期相同且ttt恰好是周期的整数倍但此时ttt时刻所有灯为绿灯且期间黄灯可能出现过也可能未出现。需要判断若所有灯的周期相同且ttt是2T2T2T的整数倍则ttt时刻是绿灯但期间可能没有黄灯因为黄灯发生在T−5T-5T−5到TTT之间。因此必须确保在(0,t)(0, t)(0,t)内至少有一个灯曾变为黄灯。最简单的处理是若ttt满足绿灯条件且t0t 0t0检查是否存在某个灯在(0,t)(0, t)(0,t)内曾处于黄灯区间。由于ttt较小可以在检查时同时验证。复杂度分析每个数据集最多检查到360036003600秒每次检查O(灯数)O(\text{灯数})O(灯数)完全可接受。代码实现// Synching Signals// UVa ID: 467// Verdict: Accepted// Submission Date: 2016-07-18// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structinstant{intseconds,increment;booloperator(instant x)const{returnsecondsx.seconds;}};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;string line;while(getline(cin,line)){vectorintcycles;intcycle;istringstreamiss(line);while(isscycle)cycles.push_back(cycle);sort(cycles.begin(),cycles.end());priority_queueinstanttimes;for(inti0;icycles.size();i)times.push((instant){cycles[i]*2,cycles[i]*2});while(times.empty()false){instant xtimes.top();times.pop();intallGreentrue;for(inti0;icycles.size();i){if((x.seconds/cycles[i])%20(x.seconds%cycles[i])(cycles[i]-5))continue;else{allGreenfalse;break;}}if(x.seconds3600){coutSet cases is unable to synch after one hour.\n;break;}elseif(allGreen){coutSet cases synchs again at ;coutx.seconds/60;cout minute(s) and ;coutx.seconds%60;cout second(s) after all turning green.\n;break;}else{x.secondsx.increment;times.push(x);}}}return0;}