蓝桥杯 2018年决赛C/C++B组 #4 调手表 （BFS、模拟）-- 酱懵静

2018决赛真题C/C++B组 调手表

问题描述
小明买了块高端大气上档次的电子手表，他正准备调时间呢。
在M78星云，时间的计量单位和地球上不同，M78星云的一个小时有n分钟。
大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是0，那么按一下按钮就会变成1，再按一次变成2。如果当前的数是n-1，按一次后会变成0。
作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多1，则要按n-1次加一按钮才能调回正确时间。
小明想，如果手表可以再添加一个按钮，表示把当前的数加k该多好啊……
他想知道，如果有了这个+k按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。
注意，按+k按钮时，如果加k后数字超过n-1,则会对n取模。
比如，n=10,k=6的时候，假设当前时间是0，连按2次+k按钮，则调为2。

输入格式
一行两个整数n,k，意义如题。

输出格式
一行一个整数表示：按照最优策略按键，从一个时间调到另一个时间最多要按多少次。

样例输入： 5 3
样例输出： 2

样例解释
如果时间正确则按0次。否则要按的次数和操作系列之间的关系如下：
1：+1
2：+1,+1
3：+3
4：+3,+1

数据范围
对于30%的数据0<k<n<=5
对于60%的数据0<k<n<=100
对于100%的数据0<k<n<=100000

资源约定：
峰值内存消耗（含虚拟机）<256M，CPU消耗<1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…”的多余内容。

注意：
main函数需要返回0;
只使用ANSIC/ANSI C++标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中#include
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

---

---分割线---

---

思路一：广度优先搜索
可以把这一系列的点视为一个图中的散点，这样你的任务就变成了在一个有限集合内，去求出遍历完这所有点所需要的最小步数，反正点也不多，总会全部进队列的，也总会结束BFS的。
话都到了这个点上，显然是让我们利用广度优先搜索了（寻找最小步骤）
下面直接给出代码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int MAX=100005;
int dp[MAX];
int n,k;

void bfs()
{
	queue<int> q;	
	q.push(0);
	dp[0]=0;
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		if(dp[(p+1)%n]==-1)			//下一点若未走则记录步数并入队列 
		{
			dp[(p+1)%n]=dp[p]+1;
			q.push((p+1)%n);
		}
		if(dp[(p+k)%n]==-1)		   //下k点若未走则记录步数并入队列 
		{
			dp[(p+k)%n]=dp[p]+1;
			q.push((p+k)%n);
		}
	}
}

int main()
{
	memset(dp,-1,sizeof(dp));	  //包含于cstring中，这里必须全设为-1，不能为0
	cin>>n>>k;
	bfs();
	int ans=dp[0];
	for(int i=1;i<n;i++) ans=ans>dp[i]?ans:dp[i];
	cout<<ans<<endl;
	return 0;
}

---

---分割线---

---

思路二：模拟
我们可以去模拟这个调时间的过程，而最后停止的标志，是所有的点都已走过。
这里可以用一个循环去对每一个和当前步数相同的点进行继续加时，这个能够保证你走的每个点都将是在最优策略下走的最小步数（初始点dp[0]当然为0喽，由于在后面需要区别时间点是否全部走过，故你需要初始化所有dp中的点为-1）。
模拟过程中，不用管那些在之后会被覆盖的时间点，反正最后的退出条件是所有点均被访问过，故最终退出时，输出的步数steep即为最大的那个步数，也就是我们所需要的答案。

#include<iostream>
#include<cstring>
using namespace std;
const int MAX=100005;
int main()
{
	int dp[MAX];
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	int n,k;
	cin>>n>>k;
	int steep=0;
	while(1)
	{
		int i;
		for(i=0;i<n;i++)
			if(dp[i]==steep)
			{
				dp[(i+1)%n]=steep+1;
				dp[(i+k)%n]=steep+1;
			}
		++steep;
		for(i=1;i<n;i++)
			if(dp[i]==-1) break;
		if(i==n) break; 
	}
	//for(int i=0;i<n;i++) cout<<" "<<dp[i];
	//cout<<endl; 
	cout<<steep<<endl;
	return 0;
}