第三题 限速路段 【题目描述】 园博会的某路段上有 N 个路牌，相邻两个路牌之间间隔 10 千米，这些路牌 将这个路段划分为等间距的 N-1 个区间。路牌有两种类型：(1)限速，接下来的 全部区间的速

第三题 限速路段dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【题目描述】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
园博会的某路段上有 N 个路牌，相邻两个路牌之间间隔 10 千米，这些路牌dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
将这个路段划分为等间距的 N-1 个区间。路牌有两种类型：(1)限速，接下来的dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
全部区间的速度都不能超过标识值；(2)取消限速，取消最近的一个与标识值相dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
同的限速。其中，限速路牌用正整数表示，取消限速路牌用负整数表示，其真实dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
标识值等于输入数据的绝对值。例如，60 表示限速 60 的路牌，而-60 表示取消dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
限速 60 的路牌。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
假设车辆在通过路牌的瞬间可以立即变速，那么通过此路段且不违反限速的dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
最短用时是多少？多个限速同时生效时，车辆的速度应不超过有效的最低限速。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
本题中速度单位均为千米每小时。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入的第 1 行包含 2 个整数 N, M，依次表示路牌的数量和车辆的最高时速。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 1 行 N 个整数，按顺序表示遇到的路牌。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出 1 行 1 个数，表示答案。保留两位小数输出。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 1】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 100dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10 -10 30 20 40dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1.93dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 1 说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
在第 1 个区间速度 10，用时 1；第 2 个区间速度 100，用时 0.1；第 3 个区dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
间速度 30，用时1⁄3；第 4 个区间速度 20，用时 0.5。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
赛事名称 限速路段dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第 7 页 共 9 页dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 2】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
6 100dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
40 40 -40 30 30 30dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1.42dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 2 说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
在第 3 个区间，取消了一个限速 40，但还有另一个限速 40 生效，因此速度dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
仍然为 40。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 3】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 100dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10 40 -40 1dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3.00dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 3 说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
在第 3 个区间，取消了限速 40，但限速 10 仍然生效。车辆在最后一块路牌dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
停下，因此最后一块路牌的指示没有影响。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 4】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 100dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
50 40 -40 1dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
0.65dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例 4 说明】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
在第 3 个区间，取消了限速 40，但限速 50 仍然生效。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据范围与约定】dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于全部数据，有1 ≤ N ≤ 105，1 ≤ M ≤ 100，−100 ≤ 路牌数值 ≤ 100。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入数据中不含有 0。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
测试点 1~4（共 40 分）：N ≤ 4000。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
测试点 5~10（共 60 分）：无特殊限制。dX9100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库