本文共 1753 字,大约阅读时间需要 5 分钟。
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
OutputLine 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input5 17
Sample Output4
n只有三种变换情况,+1,-1,x2,求n最少能经过多少步成为k。
乍看很简单,对三种情况BFS就行了,但这个数据很大,容易TLE或者RE。 我第一次TLE,之后就设置了一个观察数组,如果某次BFS时又碰到了这个数,这时的次数肯定不是最小的。 第二次RE,又考虑了n大于k的情况,这时候肯定只能一直-1,所以特判。又x2的操作容易超数组,所以如果某次x2超过了目标的两倍,那肯定是没用的,剪掉。到达负数也不行,剪掉。最后就过了#include#include #include #include #include #include #include #include #include #include
转载地址:http://yicvb.baihongyu.com/