机制的外卖员【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%内容,购买单篇文章或订阅会员后查看


隐藏内容

此处内容需要权限查看

  • 普通用户特权:11金币
  • 会员用户特权:免费
  • 永久会员用户特权:免费推荐
会员免费查看