历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1100. 抓住那头牛（玄学优化）原题链接简单

作者：

hyc_noi , 2020-06-30 18:14:03 , 所有人可见 , 阅读 5871

92

7

特别鸣谢

1、感谢 @add 提出原文$t->t+1$的表述可能有歧义，并让我发现这里有一个笔误

题目描述

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 $N$，牛位于点 $K$。

农夫有两种移动方式：

从 $X$ 移动到 $X−1$ 或 $X+1$，每次移动花费一分钟
从 $X$ 移动到 $2∗X$，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数$N$和$K$。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

$0≤N,K≤105$

样例

输入样例：

5 17

输出样例：

算法1

(普通的bfs)

有三种情况，每次都扩展题目里的三种状态就行了。为了不出现死循环，这里要判个重。如果之前有步数记录，则说明走过这个地方，不考虑。

算法2

(我的玄学优化bfs)

其实可以发现，虽然数轴是无限的，但是如果到了零以下，是没有牛的，而且则只有一种方案可以让农夫重新到正数：$t$走到$t+1$~~(这不是自讨苦吃嘛，走的还更远了。我相信农夫不会傻到这种程度)~~
然后，我们又发现，加一也不能大于牛最大可能在的地方（这个大家都懂吧）。
最后可以发现，如果从牛最大可能在的地方再乘2，就必须往回走了。而且如果先往回走再乘2，一定更优。因为如果那样的话，就相当于一次性走了两步。所以，一定不会大于牛最大可能在的地方。而且，因为1e5是一个偶数，所以乘2后一定是两格两格走，不会有特殊情况。如果是奇数可能会出现本来只走一格，先减一再乘2后还是走一格。

嗯，等等，是不是只有这一个特殊情况呢？

没错，你的猜想是对的，所以，是奇数就减一再与k比较。我们成功优化。

你以为这样就完了吗？

不可能的！

不难发现，如果一个数大于k，则只能选择从$t$走到$t-1$的方法。所以我们可以判断一下，t是否大于k。如果大于，则只执行从$t$走到$t-1$。当然，我们还可以在开始判断一下，如果是，则直接输出$n-k$。

你以为这样就完了吗？

真的完了。（本蒟蒻想不出来了）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int NN=1e5;
int n,k,sum[NN+4];
int bfs()
{
    queue<int>q;
    q.push(n);
    while(q.size())
    {
        int t=q.front();
        if(t==k)
            return sum[t];
        q.pop();
        if(t+1<=NN&&t+1<=k&&!sum[t+1])//玄学优化
        {
            sum[t+1]=sum[t]+1;
            q.push(t+1);
        }
        if(t-1>=0&&!sum[t-1])//玄学优化
        {
            sum[t-1]=sum[t]+1;
            q.push(t-1);
        }
        if(t*2<=NN&&t*2-(k&1)<=k&&!sum[t*2])//玄学优化
        {
            sum[t*2]=sum[t]+1;
            q.push(t*2);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    if(n>k)//玄学优化
    {
        printf("%d",n-k);
        return 0;
    }
    printf("%d",bfs());
    return 0;
}

优化代码
https://www.acwing.com/problem/content/submission/code_detail/1778730/
少量优化~~(因为不优化会数组越界)~~
https://www.acwing.com/problem/content/submission/code_detail/1778693/
~~优化了一半的时间，数据大点可以保证不TLE~~

到了最后了，本蒟蒻写一篇题解也不容易，希望各位大佬点一下那个向上的三角支持我一下，谢谢！

19 评论

xiuzhiyuan 2022-02-11 12:21

话说代码好像真的打不开

jieHeEternity 2021-08-16 19:47

这个题感觉把数组换成哈希表就可以了吧

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+10;
int a[N];

unordered_map<int,int>dist;



int n,k;
queue<int>q;
int dx[]={1,-1};

void bfs(int sta)
{
    dist[sta]=0;
    q.push(sta);


    while(q.size())
    {
        auto t=q.front();
        q.pop();

        int x1=t-1,x2=t+1,x3=t*2;
        for(int i=0;i<2;i++)
        {
            int x=t+dx[i];
            if(dist[x]==-1)
            {
                dist[x]=dist[t]+1;

                q.push(x);
            }
        }
        if(dist[x3]==-1)//由于是宽搜，确保这个点时第一次搜到
        {

            dist[x3]=dist[t]+1;
            q.push(x3);
        }

    }

}
int main()
{

    cin>>n>>k;
    for(int i=-N;i<=N;i++)dist[i]=-1;
    bfs(n);



    cout<<dist[k]<<endl;

    return 0;

}