- 题目链接：http://noi.openjudge.cn/ch0205/2971/
- 总时间限制: 2000ms 内存限制: 65536kB
- 描述
-
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟2、从X移动到2*X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？ - 输入
- 两个整数，N和K
- 输出
- 一个整数，农夫抓到牛所要花费的最小分钟数
- 样例输入
-
5 17
- 样例输出
-
4
算法分析：
农夫在每个点都有三条路可以选择，即类似于：在每一个结点都有三个相邻的结点。现在需要最短时间找到牛，所以用广搜是比较容易解决的。关键是要理清楚数据结构的问题。
1 #include<stdio.h> 2 #include<queue> 3 #include<iostream> 4 using namespace std; 5 #define MAXINDEX 200010 6 //MAXINDEX的值达到K的2倍应该就可以了。但是在搜索过程中要注意不能越界。 7 int N,K; 8 int s[MAXINDEX]={0};//s[i]=t表示从出发点到达坐标i需要t分钟。 9 queue<int> q; 10 11 void BFS(); 12 int main(int argc, char *argv[]) 13 { 14 scanf("%d%d",&N,&K); 15 s[N]=1;//s[i]=0表示没有到达过坐标i这个地方。为了标记出起点，把s[N]设为1， 16 BFS(); 17 printf("%d\n",s[K]-1); //起点的步数是1，所以每个点的步数都多了1，应该减掉1. 18 return 0; 19 } 20 21 void BFS() 22 { 23 int i,nowIndex,newIndex; 24 if(N==K) return ; 25 26 q.push(N); 27 while(!q.empty()) 28 { 29 nowIndex=q.front(); 30 for(i=0;i<3;i++) 31 { 32 if(i==0) newIndex=nowIndex-1; 33 else if(i==1) newIndex=nowIndex+1; 34 else newIndex=nowIndex*2; 35 36 if(newIndex>=0&&newIndex<MAXINDEX&&s[newIndex]==0) 37 { 38 s[newIndex]=s[nowIndex]+1; 39 q.push(newIndex); 40 if(newIndex==K) return; 41 } 42 } 43 q.pop(); 44 } 45 }
时间复杂度约为log2(K/N)+x,其中x是2^t与K之差. (2^t是与K最接近的2的幂次值).
