蓝桥杯2018年第九届真题-调手表【C++代码】

题目大意：

这个题目有点绕，我帮大家捋一捋题意，就是说小明现在手表上有两个按键，一个按下去时间+1，一个按下去时间+k，然后题目问的是在一个0–n-1的时间差里，调到这里面任意一个时间所需要的最小步数的最大值。

例如：样例当总时间为n=5,按键k=3：
调到0所需要的最小步数：0 不用动
调到1所需要的最小步数：1 按+1键
调到2所需要的最小步数：2 先按+1键 再按+1键
调到3所需要的最小步数：1 按+3键
调到4所需要的最小步数：2 按+3键 再按+1键
因此答案为这里面所有最小步数的最大值，即2，即任何一个时间点最多只需要按两次就能调过来。

解题思路：
BFS的思想，用一个队列先存储第一个走到的时间状态，即时间0，步数为0，然后根据队首元素往后搜可能到达的两个时间点（即+1之后的时间和+k之后的时间），如果这两个时间没有走过那就存进队列，对应时间状态的步数+1，最后找到这些步数里的最大值就行。

参考代码:

#include <bits/stdc++.h>
using namespace std;
int ans=0,n,k,t,book[100001];
typedef struct
{ int num;//当前状态里的时间 
  int step; //走到这个状态所需要的步数 
}Status;//定义状态结构体 
queue<Status> q;
int main() 
{ 
      cin>>n>>k;
      Status start,f,now1;//起始    首元素    当前状态 
      start.step=0;
      start.num=0;
      book[0]=1;
      q.push(start);//先插入当前状态 
      while(!q.empty())
      {
          f=q.front();//取出首元素
          q.pop();
          t=(f.num+1)%n;//按+1键后的时间 
          if(!book[t])//如果这个时间没有走过 
          { book[t]=1;//标记走过 
          now1.num=t;
            now1.step=f.step+1;
            ans=max(ans,now1.step); //更新答案 
            q.push(now1);//把当前状态插入 
          }
          t=(f.num+k)%n;//按+k键后的时间 
          if(!book[t])//如果这个时间没有走过
          { book[t]=1;//标记走过 
          now1.num=t;
            now1.step=f.step+1;
            ans=max(ans,now1.step);
            q.push(now1);//把当前状态插入
          }
          
      }
      cout<<ans;
    return 0;
    
}