UVa 617 Nonstop Travel
题目描述
菲尔上夜班，每天凌晨2:002:002:00准时离开公司的停车场。回家的路是一条直路，路上有一个或多个交通信号灯。菲尔一直想知道，给定每个信号灯的位置和周期，是否存在某个速度，使他能够在不因红灯而加速或减速的情况下顺利通过所有信号灯。你需要编写程序找出所有满足条件的整数速度（英里/小时）。速度范围为303030到606060英里/小时（含）。他可以在信号灯由黄变红的瞬间或由红变绿的瞬间通过。注意：所有信号灯在凌晨2:002:002:00同时开始绿灯周期。
输入格式
输入包含一组或多组数据，每组描述一组交通信号灯，最后以-1结束。每组数据的第一行为一个整数NNN（N≤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个信号灯所用的时间ti=Livt_i = \frac{L_i}{v}ti=vLi小时，转换为秒：ti=Li×3600vt_i = \frac{L_i \times 3600}{v}ti=vLi×3600秒。
信号灯的周期为Pi=Gi+Yi+RiP_i = G_i + Y_i + R_iPi=Gi+Yi+Ri，在一个周期内，绿灯和黄灯的持续时间总和为Ti=Gi+YiT_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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structSignal{doubleL,G,Y,R,P,Rs;}signals[10];intmain(){intn,cases=0,speed[100];while(cin>>n,n>=0){cout<<"Case "<<++cases<<':';for(inti=0;i<n;i++){cin>>signals[i].L>>signals[i].G>>signals[i].Y>>signals[i].R;signals[i].P=signals[i].G+signals[i].Y+signals[i].R;signals[i].Rs=signals[i].G+signals[i].Y;}memset(speed,0,sizeof(speed));for(inti=30;i<=60;i++){boolacceptable=true;for(intj=0;j<n;j++){doublearrived=fmod(signals[j].L*3600/i,signals[j].P);if(arrived>signals[j].Rs+1e-7){acceptable=false;break;}}speed[i]=acceptable?1:0;}booloutputed=false;intk=30;while(k<=60){if(speed[k]==1){if(outputed)cout<<',';elseoutputed=true;cout<<' '<<k;intlength=0;while(k<=60&&speed[k]==1)length++,k++;if(length>1)cout<<'-'<<(k-1);}elsek++;}if(!outputed)cout<<" No acceptable speeds.";cout<<'\n';}return0;}总结
本题通过枚举所有候选速度，并利用取模运算判断每个信号灯到达时的状态，从而筛选出可行速度。核心是正确计算到达时刻在一个周期内的相对位置，并注意浮点数精度处理。由于候选速度范围很小，暴力枚举是最高效且简洁的方法。输出时需要将连续速度合并为区间，注意格式控制（逗号、空格、换行等）。本题也提醒我们在处理时间与速度的关系时，注意单位换算（小时与秒的转换）。