企业官网建设流程全解析

题目描述

题目要求计算一组交通信号灯在初始全部为绿灯后，第一次再次全部变为绿灯（且在此之前至少有一个信号灯变为黄灯）的时间。每个信号灯的周期为TTT秒，其中绿灯持续T−5T-5T−5秒，黄灯持续555秒，红灯持续TTT秒（因此一个完整周期为2T2T2T秒，包括绿灯、黄灯和红灯）。初始时刻所有信号灯均为绿灯开始。需要找到最小的t>0t > 0t>0（以秒为单位），使得在ttt时刻所有信号灯均为绿灯，且存在某个信号灯在(0,t)(0, t)(0,t)区间内曾变为黄灯。若t>3600t > 3600t>3600秒（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⌋，S=t mod 60S = t \bmod 60S=tmod60。

样例

输入

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.

题目分析

本题的核心是模拟信号灯的状态变化，并寻找所有灯同时为绿灯的最小时间点t>0t > 0t>0，且满足在(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)决定：

• 若r<T−5r < T-5r<T−5：绿灯
• 若T−5≤r<TT-5 \le r < TT−5≤r<T：黄灯
• 若r≥Tr \ge Tr≥T：红灯

初始时刻t=0t=0t=0所有灯均为绿灯（r=0r=0r=0）。

同步条件

寻找最小的t>0t > 0t>0，使得对每个灯iii，t 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满足条件且t>0t > 0t>0，则输出；否则将ttt增加其步长继续。

黄灯条件的判断

由于初始时刻所有灯为绿灯，第一个同步时间ttt必然大于000。只需检查ttt之前是否有黄灯发生。实际上，由于初始状态是绿灯，任何t>0t > 0t>0都会经历至少一个灯的黄灯（除非所有灯周期相同且ttt恰好是周期的整数倍？但此时ttt时刻所有灯为绿灯，且期间黄灯可能出现过也可能未出现。需要判断：若所有灯的周期相同，且ttt是2T2T2T的整数倍，则ttt时刻是绿灯，但期间可能没有黄灯（因为黄灯发生在T−5T-5T−5到TTT之间）。因此必须确保在(0,t)(0, t)(0,t)内至少有一个灯曾变为黄灯。最简单的处理是：若ttt满足绿灯条件且t>0t > 0t>0，检查是否存在某个灯在(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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structinstant{intseconds,increment;booloperator<(instant x)const{returnseconds>x.seconds;}};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;string line;while(getline(cin,line)){vector<int>cycles;intcycle;istringstreamiss(line);while(iss>>cycle)cycles.push_back(cycle);sort(cycles.begin(),cycles.end());priority_queue<instant>times;for(inti=0;i<cycles.size();i++)times.push((instant){cycles[i]*2,cycles[i]*2});while(times.empty()==false){instant x=times.top();times.pop();intallGreen=true;for(inti=0;i<cycles.size();i++){if((x.seconds/cycles[i])%2==0&&(x.seconds%cycles[i])<(cycles[i]-5))continue;else{allGreen=false;break;}}if(x.seconds>3600){cout<<"Set "<<++cases<<" is unable to synch after one hour.\n";break;}elseif(allGreen){cout<<"Set "<<++cases<<" synchs again at ";cout<<x.seconds/60;cout<<" minute(s) and ";cout<<x.seconds%60;cout<<" second(s) after all turning green.\n";break;}else{x.seconds+=x.increment;times.push(x);}}}return0;}