php自建网站,做企业网站备案收费吗,网站建设与 宣传关系,苏州个人网站制作#先看题目
题目描述
地上有一排格子#xff0c;共 n 个位置。机器猫站在第一个格子上#xff0c;需要取第n 个格子里的东西。
机器猫当然不愿意自己跑过去#xff0c;所以机器猫从口袋里掏出了一个机器人#xff01;这个机器人的行动遵循下面的规则#xff1a;
初始时…#先看题目
题目描述
地上有一排格子共 n 个位置。机器猫站在第一个格子上需要取第n 个格子里的东西。
机器猫当然不愿意自己跑过去所以机器猫从口袋里掏出了一个机器人这个机器人的行动遵循下面的规则
初始时机器人位于 1 号格子若机器人目前在 x 格子那么它可以跳跃到 x−1,x1,2x 里的一个格子不允许跳出界
问机器人最少需要多少次跳跃才能到达 n 号格子。
输入格式
仅一行一个正整数表示 n。
输出格式
仅一行一个正整数表示最少跳跃次数。
输入输出样例
输入 #1
30
输出 #1
6
输入 #2
50
输出 #2
7
输入 #3
64
输出 #3
6
输入 #4
63
输出 #4
8
说明/提示
样例解释
第一组样例 1→2→4→8→16→15→301→2→4→8→16→15→30
第二组样例 1→2→3→6→12→24→25→501→2→3→6→12→24→25→50
第三组样例 1→2→4→8→16→32→641→2→4→8→16→32→64
第四组样例 1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63
请注意在本组样例中63 不能通过 64−1 得到因为格子总数为 63 没有第 64 个格子。
数据规模与约定
对于 100% 的数据有 1≤n≤1000000。
题目链接https://www.luogu.com.cn/problem/B3626
#思路
要找最短路所以要用BFS。
#最后附上完整代码
#includebits/stdc.h//万能头文件
using namespace std;
int vis[1000010],n;
queueint q;//定义队列
void bfs()
{memset(vis,-1,sizeof vis);q.push(1);vis[1]0;while(!q.empty()){//队列不为空就一直执行int tq.front();q.pop();if(tn){//因为BFS是按层遍历所有第一次搜出的就是最短路coutvis[n];return;}if(t-11t-1nvis[t-1]-1){//搜过的地方不重复搜q.push(t-1);vis[t-1]vis[t]1;}if(t11t1nvis[t1]-1){//注意边界q.push(t1);vis[t1]vis[t]1;}if(t*21t*2nvis[t*2]-1){q.push(t*2);vis[t*2]vis[t]1;}}return;
}
int main()
{cinn;bfs();return 0;//华丽收尾
}
