1到n的最小步数

1到n的最小步数

Time Limit: 1 Sec  Memory Limit: 128 MB

给你一个数n，让你求从1到n的最小步数是多少。

对于当前的数x有三种操作：

1：  x+1

2：  x-1

3：  x*2

Input

测试数据为多组，对于每组测试数据：（大约1000组）

输入一个正整数n（1 <= n <= 1000000）

Output

对于每组测试数据输入从1到n的最小步数ans

Sample Input

3

8

Sample Output

2

3

这道题就是BFS模板题，但是又有点区别，测试数据组数比较多，直接写容易超时，所以要用到预处理

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e6+;

int cnt[maxn*];

int n,t;

void bfs(){

    queue<int>q;

    q.push();

    while(!q.empty()){

        int x=q.front(),xx;

        if(t==maxn)

            return ;

        for(int i=;i<;i++){　　　　///进行  +1  -1  *2   3种操作

            if(i==){

                xx=x+;

            }

            else if(i==){

                xx=x-;

            }

            else{

                xx=x*;

            }

            if(xx<||xx>maxn||cnt[xx]||xx==)　　///判断操作后是否满足条件

                continue;

            cnt[xx]=cnt[x]+;　　///操作数 + 1

            q.push(xx);　　

            t++;         ///直接 搜索1e6次

        }

        q.pop();

    }

}

int main(){

    bfs();

    while(~scanf("%d",&n)){

        printf("%d\n",cnt[n]);

    }

    return ;

}