一道题带你认识ACM竞赛

说明：这是我们学校ACM公众号的一篇推送，我感觉我写的挺好的，顺便放在博客当纪念啦~！

以下是正文，排版原因，改成适合博客阅读的方式：

​

这一篇推送将带你们真真正正走近ACM比赛的世界。

阅读此文章你需要简单的C或C++编程基础，没有编程基础也没关系，我们会由浅入深，用最简单易懂的语言去介绍。

  ·  什么是编程？

          引用用百度百科里面的介绍就是：

                编程是编写程序的中文简称，就是让计算机代为解决某个问题，对某个计算体系规定一定的运算方式，是计算体系按照该计算方式运行，并最终得到相应结果的过程。

  ·   什么意思呢？

        就像我们解数学题，看完题目你会做了，你脑袋里有思路，但是应该怎么表达出来呢？这个时候你就要需要数学符号，用数学的语言去解释这道题目应该怎么解。然后数学老师就会看懂你的话，并理解你的思路。

        同样的，我们在编写程序的时候，我们就需要一种计算机的语言，计算机能明白能看懂并执行的语言。我们所说的编程，就是用计算机的语言，告诉计算机去做什么。我们平常所提到的 C语言，C++语言，Python语言，JAVA语言，就是计算机常用语言。

       

        我们的ACM比赛就是用计算机语言，去解决各种问题，类似于数学竞赛，用数学语言去解决数学问题。所以ACM是一个挑战性极强的竞赛！接下来，我将用一道简单但又不简单的题目，带你们了解ACM。

母牛的故事

        从前有一个农夫，他的名字叫做约翰。他养了很多很多头母牛。突然有一天，一只调皮的母牛走丢了，农夫要尽快的抓住她，不然她就又跑掉了！现在我们将问题简单化。假设农夫和母牛都站在一条数轴上，农夫开始的位置为N，母牛的位置为K。

       约翰有三种行动方式，每行动一次需要一秒钟时间，假设农夫的现在的位置为X，他可以向前走一格到X+1，也可以向后走一格走到X-1，他还可以传送！一下子走到了2*X。

       那么我们的问题是，假设母牛不会动，农夫最少需要多少秒才能抓到母牛？

 输入：输入包括两个整数，用空格隔开，分别为N和K。其中0<=N,K<=100000。

      

 输出：一个整数T，代表农夫所需的最少时间。

   原题链接：http://poj.org/problem?id=3278

       以上就是我们常见的ACM题目描述啦！如果用数学的方式去描述，就是：已知N和K，N,K为题目描述的意思，求T。各位小伙伴可以思考一下怎么做。对于这种题目，我们很难用数学的方法去证明或解决。这个时候我们只能借助计算机去帮助我们解决这个问题。这个时候就需要一些编程的思想了，对于没有接触过计算机编程的同学，理解起来可能会有点难度。

  ·  题目大意

             这里我们给出一组数据，假设N=5,K=17，那么最后我们计算得到的应该是T=4.

       怎么计算得来的呢？假设我们采用全部往前走的策略，那么我们一共要走17-5=12步。这个策略明显是不对的。因为我们一开始就让5×2=10，这样可以省去很多步骤，那么我是不是只要乘得越多得到的步数就越少呢？

5→10→20→19→18→17

      当农夫的位置变为20后，这个时候他能做的只有往后走，所以我们有这样一个看似更优的策略，一直乘2直到X大于K，然后再算出往后走的步数。这样的策略算出来是5（一共走了5步），这样的策略明显跟正确的答案不一样。实际上我们有更优的策略！

5→10→9→18→17

       这个时候就复杂了，我们无法用正常的语言，或者说数学的语言去描述这种策略。这个时候应该怎么办？只能借助计算机的语言了！我们知道计算机的计算能力非常强大，我们人类不知道最优策略的时候，就可以让计算机直接帮我们暴力算出来。这个时候我们就要编写程序，让电脑帮我们计算。

       对于编程未入门者，读到这里就已经足够了！如果你已经了解编程，或者你对编程感兴趣，可以继续往下阅读。

 ·  题解

             实际上，我们直接让计算机帮我们计算出每一种情况就可以了。我们知道一开始的位置是5，那么我们可以把所有情况都枚举一遍，即试一下往前走1往后走1或乘2。然后我们再对得到的三种情况4,6,10继续重复上面的步骤得到5,3,8,7,5,12,11,9,20 。这样我们不断地得到一个越来越大的数列，最后只要看看这个数列里面有没有K，就代表我们是否到达了K，这个时候我们只要输出我们重复了多少次这个步骤，就是答案了。

       聪明的孩子或许已经想到，这其实是一个宽度优先搜索算法，我们不断地尝试每一种情况，直到找到正确答案为止。代码打起来有点复杂而且有很多的细节需要考虑。这里我讲解几个重要的细节。

1. 当农夫的位置为0的时候，他只能往前走1。

2. 当农夫的位置大于K时，他只能往后走1 。

3. 如果某个位置农夫已经走过，那么农夫不用再走到该位置。

       读者可以思考一下为什么。如果没有考虑第三点，程序会超时。第三点其实就是我们算法课上讲的剪枝，我们不必搜索我们已经搜索过的地方。最后就是我们打代码的时候了！更多细节，注意看代码的注释。代码采用C++。

  ·  代码

#include<iostream>
#include<queue>//用系统提供的队列
using namespace std;

int N,K;

//当前状态，X为农夫当前的位置，T为农夫走过的次数
struct point{
   int X;
   int T;
};

//用于标记该位置农夫是否走过
bool vis[200050];

//题目说N<=100000，所以我们要把数组定义成比100000*2大一点点的大小，防止数组越界！（有兴趣的可以用思考下为什么）

int main(){

   //输入N和K
   cin>>N>>K;

   //初始状态
   point a;
   a.X=N;
   a.T=0;

   queue<point> que;//定义一个队列（宽搜基本上都使用队列）
   que.push(a);//将该节点（即初始状态）加入队列

   //将数组初始化为0，即一开始农夫所有位置都没有走过。
   for(int i=0;i<200050;i++)
   vis[i]=0;

   //不断地提取状态，题目保证有解
   while(!que.empty()){
       point temp=que.front();//临时变量
       que.pop();

       //如果农夫当前的位置就是K，那么输出T并退出程序。
       if(temp.X==K){
           cout<<temp.T<<endl;
           return 0;
       }

       //如果往后走不是0，并且往后走的那个位置没有被走过，那么我们就把往后的情况加入到队列
       if(temp.X-1>=0&&vis[temp.X-1]==0){
           point tt=temp;
           tt.X--;//往后走
           tt.T++;//时间加1
           que.push(tt);//加入队列
           vis[temp.X-1]=1;//标记为走过
       }

       //往前走的情况
       if(temp.X<K&&vis[temp.X+1]==0){
           point tt=temp;
           tt.X++;
           tt.T++;
           que.push(tt);
           vis[temp.X+1]=1;
       }

       //乘2的情况
       if(temp.X<K&&vis[temp.X*2]==0){
           point tt=temp;
           tt.X*=2;
           tt.T++;
           que.push(tt);
           vis[temp.X*2]=1;
       }
      
   }
   
   return 0;
}