说明

该程序用于计算多个交通信号灯在初始同时变为绿灯后，再次同时显示绿灯的最短时间。每个信号灯的周期包括绿灯、黄灯和红灯时间，程序需要找到所有信号灯周期的最小公倍数，确保它们在某一时刻再次同时显示绿灯。

算法标签

• 数学计算
• 最小公倍数
• 时间处理

解题思路

1. 问题分析：每个信号灯的周期为T秒，其中绿灯时间为T - 5秒，黄灯时间为5秒。程序需要找到一个时间点t，使得对于所有信号灯，t处于它们的绿灯周期内。
2. 输入处理：读取每个场景的信号灯周期，直到遇到0结束场景，整个输入以000结束。
3. 时间计算：
   • 对于每个场景，计算所有信号灯周期的最小公倍数（LCM）。
   • 检查是否存在一个时间t（不超过5小时），使得t满足所有信号灯同时处于绿灯周期。
4. 输出结果：如果找到满足条件的t，则格式化输出小时、分钟和秒；否则输出超时信息。

分析

• 周期处理：每个信号灯的绿灯周期为T - 5秒，黄灯和红灯周期为T秒。
• 最小公倍数：计算所有信号灯周期的最小公倍数，确保它们在同一时间点再次同时显示绿灯。
• 时间限制：检查计算出的时间是否在5小时（18000秒）内。

实现步骤

1. 读取输入：循环读取每个场景的信号灯周期，直到遇到0结束场景。
2. 计算最小公倍数：对于每个场景的信号灯周期，计算它们的最小公倍数。
3. 检查时间限制：确保计算出的时间不超过5小时。
4. 格式化输出：将时间转换为小时、分钟和秒的格式输出，或输出超时信息。

代码解释

• 输入处理：使用scanf读取信号灯周期，存储在cycles中，直到遇到0结束场景。
• 最小公倍数计算：遍历所有周期，计算它们的最小公倍数。
• 时间检查：确保计算出的时间t不超过5小时（18000秒）。
• 结果输出：如果找到满足条件的t，则格式化为HH:MM:SS输出；否则输出超时信息。

该程序通过数学计算和有效的时间处理，解决了交通信号灯同步的问题，适用于类似周期性事件的同步计算。

代码：

/* UVA161 POJ1211 Traffic Lights */

#include <iostream>
#include <map>
#include <cstdio>
#include <climits>

using namespace std;

const int N = 3600 * 5;

int main()
{
    int x;
    for(;;) {
        scanf("%d", &x);
        if(x == 0) break;

        map<int, int> cycles;
        map<int, int>::iterator iter;
        int cnt = 0, minx = 1e9 + 1;
        while(x) {
            cnt++;
            minx = min(minx, x);
            cycles[x] = 1;
            scanf("%d", &x);
        }

        if(cnt >= 2) {
            int i;
            for(i = minx - 5; i <= N; i++) {
                for(iter = cycles.begin(); iter != cycles.end(); iter++) {
                    int tmp = (i / (2 * iter->first)) * (2 * iter->first);
                    if(i >= tmp + iter->first - 5) break;
                }
                if(iter == cycles.end()) {
                    int h = i / 3600;
                    i %= 3600;
                    int m = i / 60;
                    int s = i % 60;
                    printf("%02d:%02d:%02d\n", h, m, s);
                    break;
                }
            }
            if(i > N)
                printf("Signals fail to synchronise in 5 hours\n");
        }
    }

    return 0;
}