Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-红绿灯
题目 2678:

蓝桥杯2022年第十三届省赛真题-红绿灯

时间限制: 1s 内存限制: 512MB 提交: 209 解决: 69

题目描述

爱丽丝要开车去上班,上班的路上有许多红绿灯,这让爱丽丝很难过。为了上班不迟到,她给自己的车安装了氮气喷射装置。现在她想知道自己上班最短需要多少时间。 

爱丽丝的车最高速度是蓝桥杯2022年第十三届省赛真题红绿灯米每秒,并且经过改装后,可以瞬间加速到小于等于最高速的任意速度,也可以瞬间停止。 

爱丽丝家离公司有 N 米远,路上有 M 个红绿灯,第 i 个红绿灯位于离爱丽丝家 Ai 米远的位置,绿灯持续 Bi 秒,红灯持续 Ci 秒。在初始时(爱丽丝开始计时的瞬间),所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红的瞬间到达红绿灯,她会停下车等红灯,因为她是遵纪守法的好市民。 

氮气喷射装置可以让爱丽丝的车瞬间加速到超光速(且不受相对论效应的影响!),达到瞬移的效果,但是爱丽丝是遵纪守法的好市民,在每个红绿灯前她都会停下氮气喷射,即使是绿灯,因为红绿灯处有斑马线,而使用氮气喷射装置通过斑马线是违法的。此外,氮气喷射装置不能连续启动,需要一定时间的冷却,表现为通过 K 个红绿灯后才能再次使用。(也就是说,如果 K = 1,就能一直使用啦!)初始时,氮气喷射装置处于可用状态。 

输入格式

第一行四个正整数 N、M、K、V,含义如题面所述。

接下来 M 行,每行三个正整数 Ai、Bi、Ci,含义如题面所述。 

输出格式

输出一个正整数 T,表示爱丽丝到达公司最短需要多少秒。

样例输入

90 2 2 2
30 20 20
60 20 20

样例输出

80

提示

爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯,然后绿灯通过,以最高速行进 60 秒后到达第二个红绿灯,此时绿灯刚好变红,于是她等待 20 秒再次变为绿灯后通过该红绿灯,此时氮气喷射装置冷却完毕,爱丽丝再次使用瞬间到达公司,总共用时 80 秒。

对于 30% 的数据,N ≤ 100; M ≤ 10; M < K; V = 1.

对于 60% 的数据,N ≤ 1000; M ≤ 100; K ≤ 50; Bi ,Ci ≤ 100; V ≤ 10.

对于 100% 的数据,0 < N ≤ 108 ; M ≤ 1000; K ≤ 1000; 0 < Bi ,Ci ≤ 106 ; 0 < V ≤ 106 ; 0 < Ai < N; 对任意 i < j, 有 Ai < Aj

标签