当前位置：首页 > article >正文

【算法题解】Berland 路标限速问题（Follow Traffic Rules）

article 2024/12/27 8:26:20

问题描述

在 Berland 城市，有一条连接首都 Berland 和奥林匹克城市 Bercouvert 的公路。为了改善交通管理，这条路上设立了一个限速标志，限制某一段路程的最大速度。在通过这个标志之后，车辆可以恢复到任意速度。我们需要计算，Berland 的普通汽车以最优的速度完成整个路程所需的最短时间。

已知条件：

车辆的最大加速度为 aa km/h²，最大速度为 vv km/h。
公路全长为 ll 公里，其中限速标志位于起点 dd 公里的位置，限速为 ww km/h。
车辆在起点时速度为 0 km/h，最终要到达终点。

要求：

计算车辆从起点到终点的最短时间，结果保留至少 5 位小数。

输入格式：

第一行输入两个整数 aa 和 vv：

aa 表示车辆最大加速度 1≤a≤100001 \leq a \leq 10000；
vv 表示车辆最大速度 1≤v≤100001 \leq v \leq 10000。

第二行输入三个整数 l,d,wl, d, w：

ll 为公路总长度 2≤l≤100002 \leq l \leq 10000；
dd 为限速标志距离 1≤d<l1 \leq d < l；
ww 为限速标志的速度 1≤w≤100001 \leq w \leq 10000。

输出格式：

输出从起点到终点的最短时间，保留至少 5 位小数。

样例输入：

示例 1：

1 1
2 1 3

输出：

2.5000000000

示例 2：

5 70
200 170 40

输出：

8.9658746953

解题思路

基本情况分析：
- 如果限速 ww 大于或等于车辆的最大速度 vv，则限速标志的存在对行车无影响，我们只需要按照最大速度 vv 进行加速、匀速行驶和减速即可。
- 如果限速 ww 小于最大速度 vv，则需要分段计算，分别处理以下几个阶段：
  1. 从起点到限速标志前，加速到限速速度 ww 或最大速度（以较小值为准）。
  2. 通过限速标志区域，以限速速度 ww 行驶。
  3. 限速区域之后到终点，加速到最大速度 vv 或直接减速。
分段计算公式：
- 根据匀加速公式 v2=u2+2asv^2 = u^2 + 2as，可以计算加速阶段所需时间和距离；
- 匀速阶段的时间为 t=s/vt = s / v；
- 总时间为三段时间的累加。

代码实现

以下是完整的 Python 实现代码：

import math

# 函数：计算最短时间
def minimum_time(a, v, l, d, w):
    # 情况 1：限速大于等于最大速度
    if w >= v:
        # 加速到最大速度并匀速行驶
        t1 = math.sqrt(2 * l / a)
        if t1 * a <= v:  # 不需要减速
            return t1
        else:
            accel_time = v / a
            remaining_distance = l - 0.5 * v * v / a
            return accel_time + remaining_distance / v

    # 情况 2：有限速区域
    # 第一阶段：加速到限速速度或最大速度
    t_accel_to_w = math.sqrt(2 * d / a)
    if t_accel_to_w * a > w:  # 速度不能超过限速
        t_accel_to_w = w / a
        dist_accel_to_w = 0.5 * w * w / a
    else:
        dist_accel_to_w = d

    # 第二阶段：限速区域内匀速行驶
    dist_in_zone = max(0, d - dist_accel_to_w)
    t_in_zone = dist_in_zone / w

    # 第三阶段：通过限速区域后继续行驶
    t_decel_to_w = math.sqrt(2 * (l - d) / a)
    if t_decel_to_w * a > w:  # 如果需要减速
        t_decel_to_w = w / a
        dist_decel_to_w = 0.5 * w * w / a
    else:
        dist_decel_to_w = l - d

    # 返回总时间
    return t_accel_to_w + t_in_zone + t_decel_to_w

# 输入数据
a, v = map(int, input().split())
l, d, w = map(int, input().split())

# 计算最短时间
result = minimum_time(a, v, l, d, w)

# 输出结果，保留 10 位小数
print(f"{result:.10f}")