华为OD 机智的外卖员（100分）【java】A卷+B卷

华为OD统一考试A卷+B卷 新题库说明
你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。
B卷对应20022部分考题以及新出的题目，A卷对应的是新出的题目。
我将持续更新最新题目
获取更多免费题目可前往夸克网盘下载，请点击以下链接进入：

我用夸克网盘分享了「华为OD题库Java（精选50题）.zip」，点击链接即可转存。
链接：https://pan.quark.cn/s/f1a7e6aec5ac

题目类型：动态规划
题目描述：
外卖员每天在大厦中送外卖，大厦共有L层（0

输入描述
当前所处楼层N和外卖配送的目的楼层M

输出描述
送达的最短时间

样例
输入
5 17

输出
4

思路分析
这道题是一道动态规划问题，dp[i]表示到达第i层的最短时间。

初始化的时候，到N层以下需要的时间，都减去相应的楼层，即步行向下

for (int i = 0; i <= N; i++) {  // 初始化到N层以下需要的时间
    dp[i] = N - i;
}
1
2
3

转移方程为，走步行梯都是dp[i - 1] + 1，走电梯需要判断是偶数层，如果是偶数层，则dp[i / 2] + 1，如果是奇数层，则dp[(i + 1) / 2] + 2，选择走步行梯和电梯时间最短的。

参考代码：

import java.util.*;

public class wittyDeliveryMan {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        if (N >= M) {
            System.out.println(0);
            return;
        }
        int[] dp = new int[M + 1];  // dp[i]表示到达第i层的最短时间
        Arrays.fill(dp, 0);
        for (int i = 0; i <= N; i++) {  // 初始化到N层以下需要的时间
            dp[i] = N - i;
        }
        for (int i = N + 1; i <= M; i++) {  // 计算从N层到M层的最短时间
            // 计算走步行梯和坐电梯的最短时间
            if (i % 2 == 0) {  // 偶数层可以直接到2*i，时间加1
                dp[i] = Math.min(dp[i - 1] + 1, dp[i / 2] + 1);
            } else { // 奇数层需要先上或者先下，再到2*(i+1)，时间加2
                dp[i] = Math.min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2);
            }
        }
        System.out.println(dp[M]);
    }
}

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