机制的外卖员

机制的外卖员【2021-08-04】

• 外卖员小W每天在大厦中运送外卖，大厦共有L层（0<L<=10^5），
• 当小W处于第N（0<N<=L）层楼时，可以每分钟通过步行梯向上到达N+1层，或向下到达N-1层，或者乘坐电梯达到2*N层。
• 给定当前小W所处的位置N，以及外卖配送的目的楼层M，请计算出小W送达的最短时间。

解答要求

• 时间限制：C/C++ 1000ms,其他语言：2000ms
• 内存限制：C/C++ 256MB,其他语言：512MB

输入

• 输入共一行，包含两个正整数N和M，分别表示起始楼层和目的楼层。其中0 < N和 M <= 10^5

输出

• 输出1个整数，表示小W配送所需的最短时间

样例1

输入：

5 17

输出：

4

解释：

• 最短的配送路径为 5–10–9–18–17

C++ DP解法

#include <bits/stdc++.h>

using namespace std;
int n, m;

int stepSize(int n, int m)
{
    int down = 0, up = 0;
    if (n >= m)
        return 0;

    vector<int> dp(m + 1, 0);
    for (int i = 0; i <= n; i++) {
        dp[i] = n - i;
    }
    for (int i = n + 1; i <= m; i++)
    {
        down = 1 + dp[i - 1];
        up = (i % 2 == 0) ? dp[i / 2] + 1 : 2 + dp[(i + 1) / 2];

        dp[i] = min(down, up);
    }
    return dp[m];
}

int main()
{
    while (cin >> n >> m)
        cout << stepSize(n, m) << endl;
    return 0;
}

BFS解法

#include <bits/stdc++.h>

using namespace std;

struct node {
    int now, step;
};

int n, m;
int check[100005];

剩余50%内容，购买单篇文章或订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接