[C++知识库]月赛反思题C

题目C

众所周知，yh学长 is very rich，他靠着玩超级大富翁的游戏富上加富，买下了地球的半座江山（另外半座他不想要啦！）。

Of course，yh学长啥都有，这其中当然也包括养猪场。

这天，yh学长正在养猪场里跟它们一起玩，他心血来潮点了个到：“花花、茉莉、小爱、仙子……？？？仙子呢？！Where are my dear Xianzi？？？！！！”
yh学长忽然发现名为“仙子”的小粉猪不见了！Oh no！这可是他最心爱的一头猪！！！
幸好yh学长在每只猪的身上都安装了高级GPS定位导航，通过智能腕表，他可以实时知道“仙子”的位置。

yh学长从一条直线上的一个点N?(0 ≤?N?≤ 100,000) 开始，“仙子”在同一直线上的一个点K?(0 ≤?K?≤ 100,000) 上。

yh学长迫不及待地想把“仙子”带回来，他决定现在就出发去找它。
可是作为一个 richer ，可选择的交通方式实在是太多了，到底要用什么交通方式去找呢？
yh学长想起“仙子”最爱的两个交通工具—— 南瓜老年代步车 以及 超级无敌霹雳豪华完美小巧简易宇宙飞船。

南瓜老年代步车南瓜老年代步车——yh学长可以在一分钟内从任何一点X移动到X-1或X+1两点。
超级无敌霹雳豪华完美小巧简易宇宙飞船超级无敌霹雳豪华完美小巧简易宇宙飞船——yh学长可以在一分钟内从任何X点移动到2*X点。

已知“仙子”在离家出走一段时间后就反悔了，
十分地想念yh学长（这就是双向奔赴吗(Ｔ▽Ｔ)磕到了磕到了ヾ(?°?°?)ﾉﾞ），
但它太累了，于是决定在原地不动等yh学长来找它。

请问yh学长至少需要多长时间才能把它找回来？

输入

第一行输入两个整数?N?和?K

输出

输出一个整数——yh学长至少花多长时间才能把“仙子”找回来？

输入样例

5 17

输出样例

4

提示

yh学长到达“仙子”所在地的最快方法是沿着以下路径移动：5-10-9-18-17，这需要4分钟。

题意

在一维坐标上给一个动点一个定点，顶点只有进一或减一或坐标乘二。

思路

首先分成两种情况：第一是动点在顶点后面只需要一直减一就可以了，第二种是通过三种都走一遍并在走过的路上进行标记遇到标记就结束，用递归的思想，找到做快的。

第二种用队列的方法写通过三种方式都计算一遍没遇到过就输入队列遇到过就跳。直到遇见我们需要的就输出步数。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;

const int N = 1e5+5;

bool vis[N];
int step[N];
queue<int> q;

int fbs(int n,int k)
{
?? ?int head,next;
?? ?vis[n]= true;
?? ?step[n]=1;
?? ?q.push(n);
?? ?while(!q.empty())
?? ?{
?? ??? ?head= q.front();
?? ??? ?q.pop();
?? ??? ?for(int i=0;i<3;i++)
?? ??? ?{
?? ??? ??? ?if(i==0){
?? ??? ??? ??? ?next=head+1;
?? ??? ??? ?}
?? ??? ??? ?else if(i==1){
?? ??? ??? ??? ?next=head-1;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?next=head*2;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?if(vis[next]||next<0||next>=N){
?? ??? ??? ??? ?continue;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?q.push(next);
?? ??? ??? ??? ?vis[next]= true;
?? ??? ??? ??? ?step[next]=step[head]+1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?if(next==k)return step[next];
?? ??? ?}
?? ?}
}

int main()
{
?? ?int n,k,ans=0;
?? ?scanf("%d%d",&n,&k);
?? ?if(k<n){
?? ??? ?printf("d",n-k);
?? ?}
?? ?else{
?? ??? ?printf("%d",fbs(n,k));
?? ?}
?? ?return 0;
}?