A46344. 抓牛农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：1、从X移动到X-1或X+1，每次移动花费一分钟2、从X移动到2*X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？输入两个整数，N和K输出一个整数，农夫抓到牛所要花费的最小分钟数样例输…
填空题
困难
知识点
题目描述
抓牛
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
参考答案
#include<iostream>
#include<iomanip>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll int
#define MAX 100005
#define inf 100005
ll a[MAX], s, t;
int main() {
cin >> s >> t;
if (s >= t) { cout << s - t << endl; return 0; }
ll m = min(t * 2, MAX); //m是右边界
fill(a, a + m, inf);
queue<ll> q; a[s] = 0; q.push(s);
while (true) {
ll x = q.front(); q.pop();
if (x - 1 >= 0 && a[x - 1] > a[x] + 1) a[x - 1] = a[x] + 1, q.push(x - 1);
if (x + 1 < m && a[x + 1] > a[x] + 1)a[x + 1] = a[x] + 1, q.push(x + 1);
if (x * 2 < m && a[x * 2] > a[x] + 1)a[x * 2] = a[x] + 1, q.push(x * 2);
if (a[t] != inf)break;
}
cout << a[t] << endl;
}
上一题
下一题