【限时免费】20天拿下华为OD笔试之 【DP】2023Q2-高速公路休息站充电规划【闭着眼睛学数理化】全网注释最详细分类最全的华为OD真题题解_购买了一辆续航里程数达 1000 公里的某自动驾驶新能源车。某一天车辆充满电后,需

【DP】2023Q2-高速公路休息站充电规划

题目描述与示例

题目描述

小明购买了一辆续航里程数达 1000 公里的某自动驾驶新能源车。某一天车辆充满电后，需从甲城出发前往距离 D 公里远的乙城，全程走高速。车载导航提示沿途有 N 个休息站均可提供充电服务，各休息站均可实时提供当前充电排队时间，单位为小时。

请协助规划时间最优的休息站充电方案，返回最短的旅行用时。

为方便计算，高速上的行驶速度固定为 100 公里/小时。规划时可不必考虑保留安全续航里程数，汽车可以将电完全用光，1000 公里续航的汽车按 100 公里/小时，可以开 10 个小时。每次充电时间固定为 1 小时，完成后电量充满。各站点充电排队时间不会变化，充电排队过程不耗电。

输入描述

第一行表示甲乙两城的距离 D，单位为公里。 第二行表示沿途的休息站数量 N。 第三行起，每行 2 个数据，分别表示休息站离起点甲城的距离，以及充电排队所需时间，单位为小时。各休息站按离从近到远排序。 0 < = D < = 1000000 ，D 是 100 的整数倍 0 < = N < = 10000

示例一

输入

1500
4
300 2
600 1
1000 0
1200 1
1
2
3
4
5
6

输出

16
1

说明

最佳方案：只在位置为 1000 的第 3 个休息站进行充电。1500 公里的行程耗时 15 小时，充电排队 0 小时，充电 1 小时。最快旅程总计花费 16 小时

其他方案一：在第 2 个休息站进行充电，总计花费 17 小时 其他方案二：在第 2 个休息站和第 4 个休息站进行充电，总计花费 19 小时

示例二

输入

800 2
300 0
600 0
1
2
3

输出

8
1

说明

最佳方案：不进任何休息站充电。800 公里的行程耗时 8 小时

解题思路

这是一道典型的序列DP问题。

很容易发现，无论停下来充电多少次，车辆花在路上行驶的时间是固定的 D // 100，这部分时间可以先不考虑，最后再计入总和。

另外，由于充电所花费的时间一定是1小时，所以我们可以把排队和充电的时间一起考虑，即在第i个充电桩充电时，我们在这个充电桩充电停留的总时间。

故我们可以用一个列表lst这样来记录第i个充电桩的情况，lst[i] = [dis_i, time_i]，其中dis_i为第i个充电桩到起点的距离，time_i为在第i个充电桩进行充电的停留的总时间。

同时，考虑起点需要从0开始，终点距离起点为D，这两个位置都无需考虑充电时间，因此我们可以在开头、末尾分别往lst列表中加入[0, 0]和[D, 0]，表示起点和终点的位置。lst的长度为N+2。

for _ in range(N):
    dis, time = map(int, input().split())
    lst.append([dis, time+1])
1
2
3

我们考虑动态规划三部曲：

1. dp数组的含义是什么？

• dp[i]表示，如果选择在第i个充电桩进行充电，所需要花费最小总时间。注意这里不包含行驶时间，因为最后再进行整体的计算。

1. 动态转移方程是什么？

对于离起点距离为dis_i的第i个充电桩，我们考虑位于其前面的充电桩，用索引j表示。由于每一次充满电之后都可以再行驶1000公里，当

• 两个充电桩之间距离在1000公里内，即dis_i - dis_j <= 1000时，可以选择从第j个充电桩出发来到第i个充电桩，而且无需在j和i之间的任何充电桩再停下来充电。如果选择在第j个充电桩充满电后来到第i个充电桩并且充电，所花费的时间为dp[j] + time_i。由于可能有若干个满足dis_i - dis_j <= 1000的j，选择其中的最小值作为dp[i]的值。
• 两个充电桩之间距离在1000公里外，即dis_i - dis_j > 1000时，无需考虑第j个充电桩对第i个充电的影响。

上述逻辑整理为代码即

for i in range(1, N+2):
    for j in range(i-1, -1, -1):
        if lst[i][0] - lst[j][0] > 1000:
            break
        else:
            dp[i] = min(dp[j] + lst[i][1], dp[i])
1
2
3
4
5
6

1. dp数组如何初始化？

由于lst数组考虑了起点和终点，lst的长度为N+2，故初始化dp数组的长度也是N+2，由于需要计算最小花费的时间，故dp数组中的元素填充为inf。另外，在起点位置所花费的时间为0，故初始化dp[0] = 0。

dp = [inf] * (N+2)
dp[0] = 0
1
2

代码

# 题目：2023Q2-高速公路休息站充电规划
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：动态规划
# 代码看不懂的地方，请直接在群上提问

from math import inf

D = int(input())
N = int(input())

# 设定起点为0，在起点无需进行充电
lst = [[0, 0]]
for _ in range(N):
    # 输入第i个充电桩的距离和时间
    dis, time = map(int, input().split())
    # 把排队和充电的时间一起考虑，故存入time+1为停留总时间
    lst.append([dis, time+1])
# 设定终点为D，在终点处无需进行充电
lst.append([D, 0])

# dp[i]表示，在第i个充电桩进行充电
# 所需要花费最小总时间（不包含行驶时间）
# 一共有N+2个位置
dp = [inf] * (N+2)
dp[0] = 0

# 遍历所有充电桩
for i in range(1, N+2):
    # 逆序遍历第i个充电桩前面的充电桩j
    for j in range(i-1, -1, -1):
        # 如果j和i之间的距离大于1000，则无需考虑j往前的充电桩了
        # 直接break退出循环
        if lst[i][0] - lst[j][0] > 1000:
            break
        # 如果j和i之间的距离小于等于1000，则考虑dp[i]和dp[j] + lst[i][1]之间的较小值
        # dp[j] + lst[i][1]表示从第j个充电桩充满电，且来到第i个充电桩进行充电所花费的时间
        else:
            dp[i] = min(dp[j] + lst[i][1], dp[i])

# dp[-1]是到达终点D所需要的花费的充电和排队的停留总时间
# 最终的答案还要加上行驶时间D // 100
print(dp[-1] + D // 100)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(N)。dp数组所占据的空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多