首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7471

抓牛(2023.12) 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=10000…

抓牛(2023.12)

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

1、从X移动到X-1或X+1,每次移动花费一分钟

2、从X移动到2*X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

时间限制:2000

内存限制:65536

输入

两个整数,N和K

输出

一个整数,农夫抓到牛所要花费的最小分钟数


样例输入

5 17

样例输出

4
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// 参考代码1 #include &lt;bits/stdc++.h&gt; using namespace std; int b[200100]; int a[10]; queue&lt;int&gt; q; int n, k; void bfs(int x) {   q.push(x);   b[x] = 1;   while (!q.empty()) {     int s = q.front();     a[1] = s - 1;     a[2] = s + 1;     a[3] = 2 * s;     for (int i = 1; i &lt; 4; i++) {       if (b[a[i]] == 0 &amp;&amp; a[i] &gt;= 0 &amp;&amp; a[i] &lt; 100100) {         b[a[i]] = b[s] + 1;         q.push(a[i]);         if (a[i] == k) {           cout &lt;&lt; b[k] - 1 &lt;&lt; endl;         }       }     }     q.pop();   } } int main() {   cin &gt;&gt; n &gt;&gt; k;   bfs(n);   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考代码2 #include &lt;bits/stdc++.h&gt; using namespace std; int n, k; bool v[100005]; struct nod {   int x, dis; }; int main() {   cin &gt;&gt; n &gt;&gt; k;   queue&lt;nod&gt; q;   if (n == k) {     cout &lt;&lt; 0;     return 0;   }   v[n] = true;   q.push({n, 0});   while (!q.empty()) {     int l = q.size();     for (int i = 1; i &lt;= l; i++) {       if (q.front().x + 1 == k || q.front().x - 1 == k ||           q.front().x * 2 == k) {         cout &lt;&lt; q.front().dis + 1;         return 0;       }       if (q.front().x + 1 &gt;= 0 &amp;&amp; q.front().x + 1 &lt;= 100000 &amp;&amp;           !v[q.front().x + 1]) {         v[q.front().x + 1] = true;         q.push({q.front().x + 1, q.front().dis + 1});       }       if (q.front().x - 1 &gt;= 0 &amp;&amp; q.front().x - 1 &lt;= 100000 &amp;&amp;           !v[q.front().x - 1]) {         v[q.front().x - 1] = true;         q.push({q.front().x - 1, q.front().dis + 1});       }       if (q.front().x * 2 &gt;= 0 &amp;&amp; q.front().x * 2 &lt;= 100000 &amp;&amp;           !v[q.front().x * 2]) {         v[q.front().x * 2] = true;         q.push({q.front().x * 2, q.front().dis + 1});       }       q.pop();     }   }   return 0; }</pre>
这道题暂未补解析。