汽车以每秒v米的速度从A点移动到B点。动作发生在X轴上。距离A d米处有红绿灯。从时间0开始,对于第一个g秒,绿灯亮,然后在接下来的r秒内红灯亮,然后再次绿灯亮g秒,依此类推。
汽车可以立即从0加速到v,反之亦然,可以立即从v减速到0。考虑到它立即通过绿灯处的红绿灯。如果汽车在红灯刚刚开启时接近红绿灯,则没有时间通过。但是,如果它在绿灯刚刚打开的时刻接近红绿灯,它就会移动。汽车在0时离开A点。
在不违反交通规则的情况下,汽车从A点到B点的最短时间是多少?
输入整数l,d,v,g,r(1≤l,d,v,g,r≤1000,d <l) - A和B之间的距离(以米为单位),从A到交通灯的距离,汽车的速度,绿灯的持续时间和红灯的持续时间。
解
if(g*v>d)
ans = l/v // i got it
else
ceil(d/v/g+r)*(g+r)+(l-d)/v // i am not getting Please help
例子 - >假设l = 5,d = 4,v = 1,g = 2,r = 1
在t = 0时,汽车从$ A $开始
在t = 2时,灯变红,但车远离光线,所以没有问题继续移动
在t = 3时,灯再次变为绿色,每秒2美元(直到$ t = 5 $)
在t = 4时,光仍然是绿色,我们到达光线
注意 - >我们有过交通灯不用担心
在t = 5时,我们到达B点
但正确和= 7这不是我做错的最小值吗?
上面的方法被红色编码器使用,我也在下面包括他的解决方案链接。
请帮助我感到难过我试图从3天内找到正确的逻辑。
在这里,你们是我最后的希望。
问题linkproblem b
Accepted solution link of red coder
注意 - >上面接受的解决方案给出7作为输出但是我认为它应该是5.所以这不可能是错误的,因为codeforces接受了它。
是的你是对的,答案应该是5。
条件g * v > d
没有任何意义。它只是检查你是否可以在第一个绿色阶段通过红绿灯。实际上它应该是((d + v - 1) / v) % (g + r) < g
。首先,如果我们使用浮点数,我们计算用(d + v - 1) / v
(整数除法)传递交通信号灯的那一秒,这与ceil(d / v)
相同。然后用模数我们计算在绿色红色循环中我们通过交通信号灯的位置。如果结果是< g
,我们在绿色时通过它,解决方案是(double)l / v
。
您可以使用与上述模数相同的技术来获取我们必须在红绿灯处停下的秒数,然后将从开始到交通灯的时间(整秒)和从红绿灯到目的地的时间相加。或者我们可以计算在通过红绿灯时绿色红色周期结束之前所需的秒数。这就是你所做的,但你缺少大括号,所以对于浮点数,我们可以使用你的公式和其他大括号:
ceil(d / v / (g + r)) * (g + r) + (l - d) / v
。