CodeForces - 520B Two Buttons 【逆向思维 || bfs 】题解

布满荆棘的人生 2021-07-24 16:52 309阅读 0赞

> hello大家好，欢迎大家访问 林深时不见鹿 的博客，算法小白，记录学习的点滴日常，致力于通俗易懂的题解，相遇即是上上签，如有不足，还请多多指教。

### 目录 ###

*   *   *  1.题目
         *  2.思路(1) 逆向思维
         *  3.代码
         *  4思路(2) bfs
         *  5.代码

### 1.题目 ###

给定一个自然数，有两种操作，  
1.将数字乘 2。  
2.将数字减去 1。  
如果某次操作后数字不为正数，则终止。  
一开始你拥有的是数字 n 。

你的目标是得到数字 m 。为了获得这个结果，他最少需要做多少次操作？

**输入格式**  
输入一行，两个整数 n 和 m (1 ≤ n, m ≤ 104)，以空格分隔。

**输出格式**  
输出最少操作的次数。

**输入输出样例**  
**输入**  
2 3  
输出  
2  
输入  
11 1  
输出  
10  
**样例说明**  
样例1中，先乘2，再减1

样例2中，疯狂减一即可

### 2.思路(1) 逆向思维 ###

1.如果n>m，只能通过减一操作来获得m。  
2.n<=m，考虑逆向思维，n变到m需要n-1和n\*2两种操作，那么反过来由m变到n需要m+1和m/2两种操作，对应的操作数是相同的，但逆向更有助于我们思考。  
3.如果m是奇数，无法进行m/2操作，进行m+1，使其变为偶数。如果m是偶数，直接m/2，重复上述操作，直到n>=m时退出，最后的操作数再加上n-m。

### 3.代码 ###

#include<iostream>
    #include<cmath>
    using namespace std;
    int main()
    { 
    	int n,m;
    	cin>>n>>m;
    	int ans=0;
    	if(n>m) 
    	{ 
    		ans=n-m;
    	}
    	else
    	{ 
    		while(n<m) 
    	    { 
    		  if(m%2==0)
    	      { 
    	     	m/=2;
    	     	ans++;
    		  }
    		  else
    		  { 
    		  	 m++;
    		  	 ans++;
    		  }
    		}
    		ans+=n-m;
    	}
    	cout<<ans<<endl;
    	return 0;
    }

### 4思路(2) bfs ###

这道题非常类似于 [AcWing 1100. 抓住那头牛][AcWing 1100.]可以说是那道题的缩小版  
直接bfs搜索。

### 5.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring> 
    using namespace std;
    const int N=1e4+10;
    int q[N];
    int dist[N]; 
    int n,m;
    int bfs()
    { 
        memset(dist,-1,sizeof(dist));
        int hh=0,tt=0;
        q[0]=n;
        dist[n]=0;
        while(hh<=tt)
        { 
        	int t=q[hh++];
        	if(t==m)  return dist[m];
        	if(t-1<N&&dist[t-1]==-1)
        	{ 
        		dist[t-1]=dist[t]+1;
        		q[++tt]=t-1;
    		}
    		if(t*2<N&&dist[t*2]==-1)
    		{ 
    			dist[t*2]=dist[t]+1;
    			q[++tt]=t*2;
    		}
    	}
    	return -1;
    }
    int main()
    { 
       cin>>n>>m;
       cout<<bfs()<<endl;
       return 0;
    }

[AcWing 1100.]: https://www.acwing.com/problem/content/1102/