自动搬运

查看原文

来自洛谷，原作者为

	Sakura_Peng **

搬运于2025-08-24 21:33:44，当前版本为作者最后更新于2017-09-19 21:48:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

##恩.....标签上面写的是入门难度，但是当我这道题目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左右），看看有木有超过规定时间，如果超过了规定时间，就不用再想了，不要抱侥幸心理，什么假如数据比较小的可能性，这是不存在的！

###发现下面dalao的程序和我的思路几乎差不多，而且程序的实现都是大致相似的，我在我的程序里加了我自己的理解，希望对大家有帮助吧！