題目說的很亂，我整理一下
所有燈都按綠、橙、紅的順序變化，綠色持續(xù)t-5秒，橙色持續(xù)5秒，紅色持續(xù)t秒，第0時(shí)刻所有燈都是剛剛變綠。求所有燈再一次變綠的最早時(shí)刻
解法：
有一點(diǎn)要明確，所求的最早時(shí)刻肯定是所有燈中其中一盞剛剛變綠，否則我們能夠找到一個(gè)更早的時(shí)刻所有燈都是綠的。那么只要枚舉所有燈的開始時(shí)間，然后再判斷此時(shí)刻所有燈都是綠色即可。
由于題目要求時(shí)刻小于5小時(shí)，即使暴力枚舉也不過3600*5，再加上判斷復(fù)雜度，總復(fù)雜度為360000*5，應(yīng)該也能過
當(dāng)然，可以用堆來優(yōu)化，這樣能夠?qū)⒆顗膹?fù)雜度至少降低一半
代碼：
1
# include <cstdio>
2# include <queue>
3# include <cstring>
4using namespace std;
5struct node
6
{
7
int i,t;
8 bool operator<(const node &b) const
9
{
10 return t>b.t;
11
}
12 node(int id,int time):i(id),t(time){}
13
};
14int loop[101],c,start;
15priority_queue<node> q;
16bool chk(int t)
17{
18 for(int i=0;i<c;i++)
19 if(t%(2*loop[i])>=loop[i]-5) return false;
20 return true;
21}
22void print(int t)
23{
24 printf("%s%d:%s%d:%s%d\n",t/3600<10?"0":"",t/3600,(t%3600)/60<10?"0":"",(t%3600)/60,(t%3600)%60<10?"0":"",(t%3600)%60);
25}
26int main()
27{
28 while(true)
29 {
30 c=0;
31 while(!q.empty()) q.pop();
32 scanf("%d",&loop[c++]);
33 if(!loop[0])
34 {
35 scanf("%d%d",&loop[1],&loop[2]);
36 break;
37 }
38 else
39 {
40 int flag=0;
41 while(loop[c-1])
42 scanf("%d",&loop[c++]);
43 c--;
44 start=0xfffffff;
45 for(int i=0;i<c;i++)
46 if(loop[i]-5<start) start=loop[i]-5;
47 start=0;
48 for(int i=0;i<c;i++)
49 if(2*loop[i]-start<=3600*5) q.push(node(i,2*loop[i]));
50 while(!q.empty()&&!flag)
51 {
52 node top=q.top();
53 q.pop();
54 if(chk(top.t)) flag=top.t;
55 else
56 {
57 top.t+=2*loop[top.i];
58 if(top.t-start<=5*3600) q.push(top);
59 }
60 }
61 if(flag) print(flag-start);
62 else printf("Signals fail to synchronise in 5 hours\n");
63 }
64 }
65 return 0;
66}
67
68