博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【打CF,学算法——二星级】CF 520B Two Buttons
阅读量:5819 次
发布时间:2019-06-18

本文共 1976 字,大约阅读时间需要 6 分钟。

提交链接:

题面:

B. Two Buttons
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed number by two. After clicking the blue button, device subtracts one from the number on the display. If at some point the number stops being positive, the device breaks down. The display can show arbitrarily large numbers. Initially, the display shows number n.

Bob wants to get number m on the display. What minimum number of clicks he has to make in order to achieve this result?

Input

The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .

Output

Print a single number — the minimum number of times one needs to push the button required to get the number m out of number n.

Sample test(s)
input
4 6
output
2
input
10 1
output
9
Note

In the first example you need to push the blue button once, and then push the red button once.

In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.

解题:

法一:

一開始看到这题,感觉似曾相识。感觉可能能够写,最初的想法是这种。n>=m。直接输出n-m。当n<m时。m若为偶数除2,m为奇数+1除以2。一直分解m到1。并记录这个过程中m分解的过程。然后将n减到近期的m分解过程中的m上。感觉非常不靠谱。纯瞎想。结果别人敲了一下说是对的。只是不是必需这么复杂,循环 m是偶数  除以2 计数值+1 。m是奇数 加一除以2  计数值+2  直到m<n 。 最后计数值加上n-m就好了 尽管不知道为什么这样就对。可是感觉是让减法尽量早减,这样就能够降低减法的次数。

代码:

#include 
using namespace std;int main(){ int n,m,cnt=0,t,ans=0,last; cin>>n>>m; if(n>=m)cout<
<
n) { if(m%2==0) { ans++; m/=2; } else { m=(m+1)/2; ans+=2; } } ans+=(n-m); cout<
<

法二:

看了一篇题解。说是spfa爆搜,顿时给跪了。感觉好奇怪。我也没看详细题解,想了一下。是不是建一张图,10000个数,减法由x到x-1建立一条权值为1的边。乘法由n到2*n建立一条权值为1的边,最后仅仅要搜索n到m的最短路就好了。

这是我自己的想法。感觉非常巧妙,可是不会超复杂度吗?然而边不是矩阵存储的,由于10000个数。最多不会超过20000条边。

转载地址:http://flwdx.baihongyu.com/

你可能感兴趣的文章
如何基于Redis Replication设计并实现Redis-replicator?
查看>>
Linux 环境下 PHP 扩展的编译与安装 以 mysqli 为例
查看>>
laravel中 url() route() URL::asset()
查看>>
浮点数内存如何存储的
查看>>
贪吃蛇
查看>>
EventSystem
查看>>
用WINSOCK API实现同步非阻塞方式的网络通讯
查看>>
vue
查看>>
玩一玩博客,嘿嘿
查看>>
P1352 没有上司的舞会
查看>>
ios11文件夹
查看>>
【HLOJ 559】好朋友的题
查看>>
Electric Fence(皮克定理)
查看>>
【状压DP】【UVA11825】 Hackers' Crackdown
查看>>
nvl 在mysql中如何处理
查看>>
MyEclipse 快捷键
查看>>
快速傅里叶变换FFT
查看>>
大数据常用基本算法
查看>>
JavaScript学习笔记(十三)——生成器(generator)
查看>>
hibernate保存失败
查看>>