题目描述菲尔上夜班每天凌晨2:002:002:00准时离开公司的停车场。回家的路是一条直路路上有一个或多个交通信号灯。菲尔一直想知道给定每个信号灯的位置和周期是否存在某个速度使他能够在不因红灯而加速或减速的情况下顺利通过所有信号灯。你需要编写程序找出所有满足条件的整数速度英里/小时。速度范围为303030到606060英里/小时含。他可以在信号灯由黄变红的瞬间或由红变绿的瞬间通过。注意所有信号灯在凌晨2:002:002:00同时开始绿灯周期。输入格式输入包含一组或多组数据每组描述一组交通信号灯最后以-1结束。每组数据的第一行为一个整数NNNN≤6N \le 6N≤6表示信号灯数量。随后NNN行每行包含四个实数LLL、GGG、YYY、RRR分别表示信号灯位置英里、绿灯时长、黄灯时长、红灯时长秒。输出格式对于每组数据输出Case X:后接所有可行的整数速度。连续速度应合并为区间形式如L-H。若区间长度为 0则只输出单个数字。区间之间用逗号分隔。如果没有可行速度输出No acceptable speeds。样例输入1 5.5 40 8 25 3 10.7 10 2 75 12.5 12 5 57 17.93 15 4 67 -1输出Case 1: 30, 32-33, 36-38, 41-45, 48-54, 59-60 Case 2: No acceptable speeds.题目分析对于每个候选速度vvv整数30≤v≤6030 \le v \le 6030≤v≤60需要判断菲尔是否能在所有信号灯处都遇到绿灯或黄灯即非红灯。由于出发时刻固定为2:002:002:00且所有信号灯同时开始绿灯周期因此可以计算从出发到到达第iii个信号灯所用的时间tiLivt_i \frac{L_i}{v}ti​vLi​​小时转换为秒tiLi×3600vt_i \frac{L_i \times 3600}{v}ti​vLi​×3600​秒。信号灯的周期为PiGiYiRiP_i G_i Y_i R_iPi​Gi​Yi​Ri​在一个周期内绿灯和黄灯的持续时间总和为TiGiYiT_i G_i Y_iTi​Gi​Yi​。若到达时刻tit_iti​对PiP_iPi​取模后的值落在[0,Ti][0, T_i][0,Ti​]内包括端点则当前为绿灯或黄灯可通过否则为红灯不可通过。由于vvv仅有313131个候选值303030到606060直接枚举每个速度依次检查所有信号灯即可。复杂度O(31×N)O(31 \times N)O(31×N)完全可行。解题思路对于每组数据读入NNN及每个信号灯的L,G,Y,RL, G, Y, RL,G,Y,R计算周期PPP和绿灯黄灯总时长TTT。枚举速度vvv从303030到606060初始化标志acceptable true。对每个信号灯iii计算到达时刻秒的模周期余数arrived fmod(L * 3600 / v, P)。若arrived T 1e-7考虑浮点误差则说明到达时是红灯标记为不可行并跳出。若所有信号灯都通过则该速度可行。收集所有可行速度然后合并为连续区间输出。遍历速度303030到606060若当前速度可行则开始一个区间继续往后扫描直到不可行输出区间起点和终点。若区间起点等于终点只输出单个数字。区间之间用逗号分隔。若没有任何可行速度输出No acceptable speeds。复杂度分析枚举速度313131个。每个速度检查最多666个信号灯。总时间复杂度O(31×N)O(31 \times N)O(31×N)空间复杂度O(N)O(N)O(N)。代码实现// Nonstop Travel// UVa ID: 617// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structSignal{doubleL,G,Y,R,P,Rs;}signals[10];intmain(){intn,cases0,speed[100];while(cinn,n0){coutCase cases:;for(inti0;in;i){cinsignals[i].Lsignals[i].Gsignals[i].Ysignals[i].R;signals[i].Psignals[i].Gsignals[i].Ysignals[i].R;signals[i].Rssignals[i].Gsignals[i].Y;}memset(speed,0,sizeof(speed));for(inti30;i60;i){boolacceptabletrue;for(intj0;jn;j){doublearrivedfmod(signals[j].L*3600/i,signals[j].P);if(arrivedsignals[j].Rs1e-7){acceptablefalse;break;}}speed[i]acceptable?1:0;}booloutputedfalse;intk30;while(k60){if(speed[k]1){if(outputed)cout,;elseoutputedtrue;cout k;intlength0;while(k60speed[k]1)length,k;if(length1)cout-(k-1);}elsek;}if(!outputed)cout No acceptable speeds.;cout\n;}return0;}总结本题通过枚举所有候选速度并利用取模运算判断每个信号灯到达时的状态从而筛选出可行速度。核心是正确计算到达时刻在一个周期内的相对位置并注意浮点数精度处理。由于候选速度范围很小暴力枚举是最高效且简洁的方法。输出时需要将连续速度合并为区间注意格式控制逗号、空格、换行等。本题也提醒我们在处理时间与速度的关系时注意单位换算小时与秒的转换。