Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
  • Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
    If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

teleporting 远距离传送
retrieve 找回

人 抓牛,人在a point N (0 ≤ N ≤ 100,000) on a number line,牛在a point K (0 ≤ K ≤ 100,000) on the same number line,两种移动方式:走,远距离传送
走:any point X to the points X - 1 or X + 1 in a single minute
远距离传送:any point X to the point 2 × X in a single minute
牛不动,多久能抓回来

输入:Line 1: Two space-separated integers: N and K
N K
输出:Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
最少的时间抓牛

//这个log把我绕的一个晕,就这上那个网站编译不过去,在测试里结果都大概正确
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>

using namespace std;
const int MAXSIZE = 100000;

queue<int> myQueue;

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    myQueue.push(n);
    int i=0;
    int m=0;
    int arr[MAXSIZE]= {0};
    while(m!=k)
    {
        ++i;
        m=myQueue.front();
        myQueue.pop();
        myQueue.push(m+1);//存在重复遍历
        myQueue.push(m-1);
        myQueue.push(2*m);

//         if(arr[m+1]!=1)
//         {
//             myQueue.push(m+1);
//             arr[m+1]=1;
//         }
//         if(arr[m-1]!=1)
//         {
//             myQueue.push(m-1);
//             arr[m-1]=1;
//         }
//         if(arr[m*2]!=1)
//         {
//             myQueue.push(m*2);
//             arr[m*2]=1;
//         }
    }
    double t=log(2*i-1)/log(3);
    int h=floor(t);
    printf("%d\n",h);
//         printf("%d\n",floor((int)(log(2*i-1)/log(3))));
//     int o=v-1;
//     int v=ceil(log(i)/log(3))-1;
//     printf("%d\n",i);
//         printf("4\n");
//     printf("%f\n",log(2*i-1));
//     printf("%f\n",log(3));
//     printf("%f\n",t);
//     printf("%d\n",o);
}