拼多多网站策划书,德州网站收录,互联网公司排名100强营收多少,wordpress调用文章发布时间题目描述
地上有一排格子#xff0c;共 n 个位置。机器猫站在第一个格子上#xff0c;需要取第 n 个格子里的东西。
机器猫当然不愿意自己跑过去#xff0c;所以机器猫从口袋里掏出了一个机器人#xff01;这个机器人的行动遵循下面的规则#xff1a;
初始时#xff0…题目描述
地上有一排格子共 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→30
第二组样例 1→2→3→6→12→24→25→50
第三组样例 1→2→4→8→16→32→64
第四组样例 1→2→4→8→16→32→31→62→63
请注意在本组样例中63 不能通过 64−1 得到因为格子总数为 63没有第 64 个格子。
数据规模与约定
对于 100% 的数据有 1≤n≤1000000。
思路
用BFS做分为队列和结构体两种解法。
完整代码
队列
#includebits/stdc.h
using namespace std;
queuepairint,int pt;
bool v[1000001];
int n;
void bfs(int a){pt.push(make_pair(1,0));v[1]true;while(!pt.empty()){int ppt.front().first;int tpt.front().second;pt.pop();if(pa){coutt;//freopen(b.out,w,stdout);return;}if(p-11!v[p-1]){v[p-1]true;pt.push(make_pair(p-1,t1));}if(p1n!v[p1]){v[p1]true;pt.push(make_pair(p1,t1));}if(p*2n!v[p*2]){v[p*2]true;pt.push(make_pair(p*2,t1));}}
}
int main(){cinn;//freopen(a.in,r,stdin);bfs(n);return 0;
}
结构体队列
#includebits/stdc.h//T2-2
using namespace std;
struct node{int l,ans;
};
queuenode q;
int n,vis[1000010];
int main(){q.push({1,0});cinn;while(!q.empty()){node tq.front();q.pop();if(vis[t.l])continue;vis[t.l]1;if(t.l0||t.ln)continue;if(t.ln){coutt.ans;return 0;}int d1t.l-1,d2t.l1,d3t.l*2;if(d11d1nvis[d1]0){q.push({d1,t.ans1});}if(d21d2nvis[d2]0){q.push({d2,t.ans1});}if(d31d3nvis[d3]0){q.push({d3,t.ans1});}}return 0;
}
