跳跃机器人

题目描述

地上有一排格子，共 $n$ 个位置。机器猫站在第一个格子上，需要取第 $n$ 个格子里的东西。

机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：

• 初始时，机器人位于 $1$ 号格子
• 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x-1,x+1,2x$ 里的一个格子（不允许跳出界）

问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。

输入格式

仅一行，一个正整数，表示 $n$。

输出格式

仅一行，一个正整数，表示最少跳跃次数。

样例 #1

样例输入 #1

30

样例输出 #1

6

样例 #2

样例输入 #2

50

样例输出 #2

7

样例 #3

样例输入 #3

64

样例输出 #3

6

样例 #4

样例输入 #4

63

样例输出 #4

8

提示

样例解释

第一组样例：
$1\to 2\to 4\to 8\to 16\to 15\to 30$

第二组样例：
$1\to 2\to 3\to 6\to 12\to 24\to 25\to 50$

第三组样例：
$1\to 2\to 4\to 8\to 16\to 32\to 64$

第四组样例：
$1\to 2\to 4\to 8\to 16\to 32\to 31\to 62\to 63$

请注意在本组样例中，$63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 1000000$。

#include<bits/stdc++.h>
using namespace std;
inline int read();
long long i,q,w,e,r,t,y,u,o,p,s,d,f,g,h,j,l,z,x,c,v,n,m,k;
long long a[1100000],b[1100000];
int main()
{
	ios::sync_with_stdio(false); cout.tie(0); cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		b[i]=-1;
	}	
	a[1]=1;b[1]=0;
	l=1;r=2;
	while(l<r)
	{
		///cout<<a[l]<<" "<<b[a[l]]<<"         ";
		if(a[l]==n)
		{
			cout<<b[a[l]];
			return 0;
		}
		if(b[a[l]-1]==-1)
		{
			b[a[l]-1]=b[a[l]]+1;
			a[r]=a[l]-1;
			///cout<<a[r]<<" ";
			r++;
		}
		if(b[a[l]+1]==-1)
		{
			b[a[l]+1]=b[a[l]]+1;
			a[r]=a[l]+1;
			///cout<<a[r]<<" ";
			r++;
		}
		if(b[a[l]*2]==-1)
		{
			b[2*a[l]]=b[a[l]]+1;
			a[r]=2*a[l];
			///cout<<a[r];
			r++;
		}
		///cout<<endl;
		l++;
	}
	cout<<b[n];
    return 0;
}

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}