题解 P2077 【红绿灯】
Sakura_Peng · · 题解
恩.....标签上面写的是入门难度，但是当我这道题目AC的时候我还是点了普及-的难度=-=
本道题很坑！
有以下需要注意：
1.注意数据范围，如果我们直接一秒一秒的模拟的话绝对会TLE，当然我没试过.....
2.没有黄灯，所以判断的时候不要多事，加个1秒的什么的。
所以我的思路便是：
使用一个累加器为现在所耗时间（单位：S），可以直接用输入的M这个变量，也可以自己创建一个新的变量，在循环相加的时候赋初值为M就可以了。
然后我们以N个路口为循环的次数
即每一次循环就是通过了一个路口
首先先判断现在是绿灯还是红灯。
重要！！！这里需要使用mod（%）的数学整除方法。
根据平常的常识可得，我们可以将绿灯和红灯所耗时间计为一组，再把当前所耗的时间去除这个一组的和，便可以得当发车时候，这个路口红灯绿灯变换了多少次。而他们的余数（余数就是在当前路口需要等待的红灯+绿灯的时间）与这个绿灯的秒数所判断，如果余数大于绿灯那么一定说明当前在路口的时候是红灯，需要等待，算出需要等待的时间为当前路口的绿灯时间差：
即绿灯时间+红灯时间-在当前路口需要等待的红灯+绿灯的时间（就是那个余数）
否则就在路口的时候是绿灯，可以直接通过。
每循环一次最后输出便可以了。
由于是数学方法，肯定主要不能光看思路，最主要还是自己按照式子推一下试试，就知道了。所以上代码=-=
#include<stdio.h>
int main()
{
int n,m,a[100001],b[100001],c[100001],x=0,k,i;
scanf("%d%d",&n,&m);
for(i=1;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
for(i=1;i<=n;i++)
scanf("%d",&c[i]); //输入
for(i=1;i<=n;i++)
{
if (i>=2)
m+=a[i-1]; //注意是i-1，因为此程序是将第i个路口与第i-1个路口之间空隙所用时间算在第i个路口之中的
else
m+=0; //特殊判断，假如在第一个路口，就不会有两个路口中间的空隙ai
if(c[i]<m%(b[i]+c[i])) //见思路
m+=(b[i]+c[i]-m%(b[i]+c[i])); //这个红绿灯需要等待的时间
printf("%d\n",m); //输出
}
return 0;
} 反思：
这个程序是一遍过的，所以就非常兴奋啦。看到数据范围时，我们要把自己的这个思路的最坏打算的时间复杂度算出来（这里科普一个常识应该都知道，但是我还是打出来：10^7——10^8大约在1s左右），看看有木有超过规定时间，如果超过了规定时间，就不用再想了，不要抱侥幸心理，什么假如数据比较小的可能性，这是不存在的！