New Online Judge
主页
问题
来源/分类
竞赛&作业
状态
排名
常见问答
登录
注册
2064: [蓝桥杯2022初赛] 红绿灯
内存限制:256 MB
时间限制:1 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:12
通过:5
提交
提交记录
统计
题目描述
爱丽丝要开车去上班,上班的路上有许多红绿灯,这让爱丽丝很难过。
为
了上班不迟到,她给自己的车安装了氮气喷射装置。现在她想知道自己上班最
短需要多少时间。
爱丽丝的车最高速度是1/
V米每秒,并且经过改装后,可以瞬间加速到小于
等于最高速的任意速度,也可以瞬间停止。
爱丽丝家离公司有N米远,路上有M个红绿灯,第i个红绿灯位于离爱
丽丝家Ai米远的位置,绿灯持续Bi秒,红灯持续Ci秒。
在初始时(爱丽丝开
始计时的瞬间),所有红绿灯都恰好从红灯变为绿灯。
如果爱丽丝在绿灯变红的
瞬间到达红绿灯,她会停下车等红灯,因为她是遵纪守法的好市民。
氮气喷射装置可以让爱丽丝的车瞬间加速到超光速(且不受相对论效应的
影响!),达到瞬移的效果。
但是爱丽丝是遵纪守法的好市民,在每个红绿灯前
她都会停下氮气喷射。
即使是绿灯,因为红绿灯处有斑马线,而使用氮气喷射
装置通过斑马线是违法的。
此外,氮气喷射装置不能连续启动,需要一定时间
的冷却,表现为通过K 个红绿灯后才能再次使用。
(也就是说,如果K = 1,就
能一直使用啦!)
初始时,氮气喷射装置处于可用状态。
输入格式
第一行四个正整数N、M、K、V,含义如题面所述。
接下来M 行,每行三个正整数Ai、Bi、Ci,含义如题面所述。
对于30% 的数据,N≤100, M
≤
10, M < K, V = 1.
对于60% 的数据,N
≤
1000, M
≤
100, K
≤
50, Bi,Ci
≤
100, V
≤
10.
对于100% 的数据,0
<
N
≤
10^8, M
≤
1000; K
≤
1000; 0<Bi,Ci
≤
10^6, 0<V
≤
10^6, 0<Ai<N。
对任意i<j, 有Ai
<
Aj。
输出格式
输出一个正整数T,表示爱丽丝到达公司最短需要多少秒。
输入样例
复制
90 2 2 2 30 20 20 60 20 20
输出样例
复制
80
数据范围与提示
爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯,
然后绿灯
通过,以最高速行进60 秒后到达第二个红绿灯,此时绿灯刚好变红,
于是她等
待20 秒再次变为绿灯后通过该红绿灯,此时氮气喷射装置冷却完毕,
爱丽丝再
次使用瞬间到达公司,总共用时80 秒。
分类标签
进阶题
动态规划