机制的外卖员【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;
}
#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;
}
#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];
#include <bits/stdc++.h>
using namespace std;
struct node {
int now, step;
};
int n, m;
int check[100005];
#include <bits/stdc++.h>
using namespace std;
struct node {
int now, step;
};
int n, m;
int check[100005];
剩余50%内容，购买单篇文章或订阅会员后查看
隐藏内容
此处内容需要权限查看
会员免费查看声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
