大厂秋招真题【DP】华为20230921秋招T1

大厂秋招真题【DP】华为20230921秋招T1

华为20230921秋招T1-开电动汽车回家过年（留学生专场）

题目描述与示例

题目描述

新年即将来临，小明计划开新买的电动汽车回老家过年。

已知小明的工作地在上海，老家在中部某城市A。上海到城市A的距离是L公里(1 <= L <= 100000)。

小明的电动汽车的电池航程是P (1 <= P <= 100)，电池最大电量也是P（假设电动汽车行驶一公里需要消耗1度电）。如果电动车在中途电量耗尽了，将无法继续前行，也就无法到达目的地了。

已知小明出发前已经把电池充满了。途中依次经过N (1 <= N < 10000)个充电站。

第i个充电站距离城市A（终点）有Ai公里，最大可充电Bi度。

请问，小明能不能顺利地回老家过年？如果可以，请输出最少需要充电多少次；如果不可以，请输出-1。

输入描述

输入的第一行为数字N。

接下来的N行，每行包含2个数并用空格隔开，分别表示Ai Bi

最后一行包括两个数L P，并用空格隔开。

输出描述

按照题目要求输出最少次数或者-1。

示例

输入

4
4 4
5 5
11 6
15 8
25 10

输出

3

说明

小明出发时电池电量是10，距离城市A 25公里。

行驶10公里后，到达距离城市A 15公里的充电站，充电前电池电量为0，充电8度之后，再出发。

行驶4公里后，到达距离城市A 11公里的充电站，充电前电池电量为4。充电6度之后，再出发。

行驶6公里后，到达距离城市A 5公里的充电站，充电前电池电量为4，充电1度之后，再出发。

之后，可以直接开到城市A一共需要充电3次才能到达城市A。

时空限制

时间限制： C/C++ 1000ms, 其他语言2000ms

内存*限制： C/C++ 256MB，其他语言 512MB

解题思路

每一个充电站都有选和不选两种状态，所以我们可以把题目看作是路径无关、求最少选择数的01背包。

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

• dp数组是一个长度为(n+1)*(P+1)的二维矩阵，dp[i][j]表示来到第i个充电桩时，剩余电量为j，所需要的最少充电次数。
• 特别地，dp[n]表示来到A城的结果。

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

来到第i个充电桩时，假设剩余电量为j，距离下一个充电桩的距离为 A i + 1 − A i A_{i+1}-A_{i} Ai+1​−Ai​，即花费的电量为diff = a_list[i+1]-a_list[i]。如果

• 选择充电，那么充电后的电量为min(j+b_list[i], P)，即充电后电量不能超过最大电量。
  • 到达第i+1个充电桩时，剩余电量为nxt = min(j+b_list[i], P) - diff
  • 故动态转移方程为dp[i+1][nxt] = min(dp[i][j]+1, dp[i+1][nxt])
  • 注意，此处的+1表示在第i个充电桩处进行了多一次充电
• 不选择充电
  • 到达第i+1个充电桩时，剩余电量为nxt = j - diff
  • 故动态转移方程为dp[i+1][nxt] = min(dp[i][j], dp[i+1][nxt])
• 注意，上述两个动态转移方程成立的条件是nxt >= 0，即从第i个充电桩开往第i+1个充电桩时，剩余电量不能够耗尽。

for i in range(0, N):a, b = lst[i]for j in range(0, P+1):if dp[i][j] == inf:continueelse:diff = lst[i+1][0] - lst[i][0]nxt = min(j+b, P) - diffif nxt >= 0:dp[i+1][nxt] = min(dp[i][j]+1, dp[i+1][nxt])nxt = j-diffif nxt >= 0:dp[i+1][nxt] = min(dp[i][j], dp[i+1][nxt])

3. dp数组如何初始化？

• 在起点出发时，电量为满电，到达第0个充电站时，剩余电量为P-a_list[0]，此时最少充电方法数为0次。故初始化dp[0][P-a_list[0]] = 0。对于其他位置，初始化为inf

dp = [[inf] * (P+1) for _ in range(N+1)]
dp[0][P-a_list[0]] = 0

考虑完上述问题后，代码其实呼之欲出了。

代码

Python

# 题目：【DP】华为2023秋招-开电动汽车回家过年
# 作者：闭着眼睛学数理化
# 算法：DP
# 代码有看不懂的地方请直接在群上提问from math import inf# 充电站数目
N = int(input())
# 储存充电站位置、最大充电量的列表lst
lst = list()
for _ in range(N):a, b = map(int, input().split())lst.append((a, b))# 终点的距离L，电池最大容量P
L, P = map(int, input().split())# 实际有用的距离是充电站到起点的距离L-a
# 得到结果后根据距离起点的远近进行升序排序
# 注意，lst最后一个位置还储存了终点的情况，即离起点的距离为L
lst = sorted((L-a, b) for a, b in lst) + [(L, 0)]# dp数组初始化为一个长度为(n+1)*(P+1)的二维矩阵
# dp[i][j]表示来到第i个充电桩时，剩余电量为j，
# 所需要的最少充电次数
dp = [[inf] * (P+1) for _ in range(N+1)]
# 如果第0个充电站的位置，从起点无法到达，则直接输出-1
if lst[0][0] > P:print(-1)
# 否则，记录到达第0个充电站，且剩余电量为P-lst[0][0]
# 的最少充电次数为0
else:dp[0][P - lst[0][0]] = 0# 遍历所有充电站for i in range(0, N):# 第i个充电站到起点的距离a，最大可充电数ba, b = lst[i]# 遍历所有可能的电量jfor j in range(0, P+1):# 遇到inf，说明没有任何一种方式# 使得到达第i个充电站时，剩余电量jif dp[i][j] == inf:continue# 否则，考虑从第i个充电站出发# 充电或不充电，到达第i+1个充电站的情况else:# 两个充电站之间的距离diff = lst[i+1][0] - lst[i][0]# 考虑在第i个充电站充电的情况# 充电之后，不能超过最大电量nxt = min(j+b, P) - diffif nxt >= 0:dp[i+1][nxt] = min(dp[i][j]+1, dp[i+1][nxt])# 考虑不在第i个充电站充电的情况nxt = j-diffif nxt >= 0:dp[i+1][nxt] = min(dp[i][j], dp[i+1][nxt])# dp[N]表示到达终点的情况ans = min(dp[N])print(ans if ans != inf else -1)

Java

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[][] lst = new int[N][2];for (int i = 0; i < N; i++) {lst[i][0] = sc.nextInt();lst[i][1] = sc.nextInt();}int L = sc.nextInt();int P = sc.nextInt();int[][] sortedLst = new int[N + 1][2];for (int i = 0; i < N; i++) {sortedLst[i][0] = L - lst[i][0];sortedLst[i][1] = lst[i][1];}sortedLst[N][0] = L;sortedLst[N][1] = 0;Arrays.sort(sortedLst, (a, b) -> Integerpare(a[0], b[0]));int[][] dp = new int[N + 1][P + 1];for (int i = 0; i <= N; i++) {Arrays.fill(dp[i], Integer.MAX_VALUE);}if (sortedLst[0][0] > P) {System.out.println(-1);} else {dp[0][P - sortedLst[0][0]] = 0;for (int i = 0; i < N; i++) {int a = sortedLst[i][0];int b = sortedLst[i][1];for (int j = 0; j <= P; j++) {if (dp[i][j] == Integer.MAX_VALUE) {continue;}int diff = sortedLst[i + 1][0] - a;int nxt = Math.min(j + b, P) - diff;if (nxt >= 0) {dp[i + 1][nxt] = Math.min(dp[i][j] + 1, dp[i + 1][nxt]);}nxt = j - diff;if (nxt >= 0) {dp[i + 1][nxt] = Math.min(dp[i][j], dp[i + 1][nxt]);}}}int ans = Arrays.stream(dp[N]).min().orElse(Integer.MAX_VALUE);System.out.println(ans != Integer.MAX_VALUE ? ans : -1);}}
}

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>using namespace std;int main() {int N;cin >> N;vector<vector<int>> lst(N, vector<int>(2));for (int i = 0; i < N; i++) {cin >> lst[i][0] >> lst[i][1];}int L, P;cin >> L >> P;vector<vector<int>> sortedLst(N + 1, vector<int>(2));for (int i = 0; i < N; i++) {sortedLst[i][0] = L - lst[i][0];sortedLst[i][1] = lst[i][1];}sortedLst[N][0] = L;sortedLst[N][1] = 0;sort(sortedLst.begin(), d(), [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0];});vector<vector<int>> dp(N + 1, vector<int>(P + 1, INT_MAX));if (sortedLst[0][0] > P) {cout << -1 << endl;} else {dp[0][P - sortedLst[0][0]] = 0;for (int i = 0; i < N; i++) {int a = sortedLst[i][0];int b = sortedLst[i][1];for (int j = 0; j <= P; j++) {if (dp[i][j] == INT_MAX) {continue;}int diff = sortedLst[i + 1][0] - a;int nxt = min(j + b, P) - diff;if (nxt >= 0) {dp[i + 1][nxt] = min(dp[i][j] + 1, dp[i + 1][nxt]);}nxt = j - diff;if (nxt >= 0) {dp[i + 1][nxt] = min(dp[i][j], dp[i + 1][nxt]);}}}int ans = *min_element(dp[N].begin(), dp[N].end());cout << (ans != INT_MAX ? ans : -1) << endl;}return 0;
}

时空复杂度

时间复杂度：O(NP)。dp过程需要进行双重循环遍历。

空间复杂度：O(NP)。二维dp数组所占空间。

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

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

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

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

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

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

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

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