蜀山区2023年信息学竞赛试题 03题

题目描述 Description 园博会的某路段上有 N 个路牌，相邻两个路牌之间间隔 10 千米，这些路牌将这个路段划分为等间距的 N-1 个区间。路牌有两种类型:(1)限速，接下来的全部区间的速度都不能超过标识值；(2)取消限速，取消最近的一个与标识值相同的限速。其中，限速路牌用正整数表示，取消限速路牌用负整数表示，其真实标识值等于输入数据的绝对值。例如，60 表示限速 60 的路牌，而-60 表示取消限速 60 的路牌。 假设车辆在通过路牌的瞬间可以立即变速，那么通过此路段且不违反限速的最短用时是多少？多个限速同时生效时，车辆的速度应不超过有效的最低限速。本题中速度单位均为千米每小时。

输入描述 Input Description 输入的第 1 行包含 2 个整数 N, M，依次表示路牌的数量和车辆的最高时速。接下来 1 行 N 个整数，按顺序表示遇到的路牌。

输出描述 Output Description 输出 1 行 1 个数，表示答案。保留两位小数输出。

样例输入 Sample Input 【样例输入1】 5 100 10 -10 30 20 40 【样例输入2】 6 100 40 40 -40 30 30 30 【样例输入3】 4 100 10 40 -40 1 【样例输入4】 4 100 50 40 -40 1 样例输出 Sample Output 【样例输出1】 1.93 【样例输入2】 1.42 【样例输入3】 3.00 【样例输入4】 0.65 数据范围及提示 Data Size & Hint 对于全部数据，有1 ≤ N ≤ 10^5，1 ≤ M ≤ 100，−100 ≤ 路牌数值 ≤ 100。 输入数据中不含有 0。 测试点 1~4（共 40 分）：N ≤ 4000。 测试点 5~10（共 60 分）：无特殊限制。 【样例1分析】 在第 1 个区间速度 10，用时 1；第 2 个区间速度 100，用时 0.1；第 3 个区间速度 30，用时1⁄3；第 4 个区间速度 20，用时 0.5。 【样例2分析】 在第 3 个区间，取消了一个限速 40，但还有另一个限速 40 生效，因此速度仍然为 40。 【样例3分析】 在第 3 个区间，取消了限速 40，但限速 10 仍然生效。车辆在最后一块路牌停下，因此最后一块路牌的指示没有影响。 【样例4分析】 在第 3 个区间，取消了限速 40，但限速 50 仍然生效。 我是小学生，麻烦大佬回答一下