本文共 1183 字，大约阅读时间需要 3 分钟。
要解决这个问题，我们需要找到从一个时间调到另一个时间的最少按键次数。手表的时间单位与地球不同，且允许两种操作：加1和加k。我们可以使用广度优先搜索（BFS）来计算最短路径。
方法思路
问题分析：我们需要在模n的数系统中，找到从一个时间调到另一个时间的最少按键次数。允许的操作是加1和加k。 广度优先搜索（BFS）：使用BFS来计算每个节点（时间点）到起点（0）的最短距离。BFS适合最短路径问题，因为它能保证第一次到达一个节点的步数就是最短的。 初始化：创建一个数组记录每个节点的最短距离，另一个数组记录访问状态。 处理队列：从起点开始，逐步处理每个节点，计算其邻居节点，并更新最短距离。 解决代码
#include #include #include #include using namespace std;void bfs(int n, int k) { array dis; array vis; queue q; dis.fill(0); vis.fill(false); q.push(0); vis[0] = true; int max_steps = 0; while (!q.empty()) { int p = q.front(); q.pop(); int x = (p + 1) % n; if (!vis[x]) { vis[x] = true; dis[x] = dis[p] + 1; if (dis[x] > max_steps) max_steps = dis[x]; q.push(x); } int y = (p + k) % n; if (!vis[y]) { vis[y] = true; dis[y] = dis[p] + 1; if (dis[y] > max_steps) max_steps = dis[y]; q.push(y); } } return max_steps;}int main() { int n, k; cin >> n >> k; int ans = bfs(n, k); cout << ans << endl; return 0;}
代码解释
读取输入：从标准输入读取n和k的值。 BFS初始化：创建一个距离数组dis和一个访问数组vis，初始化队列并将起点（0）加入队列。 处理队列：循环处理每个节点，计算加1和加k后的结果，更新最短距离并记录访问状态。 输出结果：返回最大的最短距离作为答案。 这种方法确保了从任意一个时间调到另一个时间的最少按键次数，且时间复杂度为O(n)，适用于n较大的情况。
转载地址：http://eoao.baihongyu.com/