本文共 1183 字,大约阅读时间需要 3 分钟。
要解决这个问题,我们需要找到从一个时间调到另一个时间的最少按键次数。手表的时间单位与地球不同,且允许两种操作:加1和加k。我们可以使用广度优先搜索(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;}
dis和一个访问数组vis,初始化队列并将起点(0)加入队列。这种方法确保了从任意一个时间调到另一个时间的最少按键次数,且时间复杂度为O(n),适用于n较大的情况。
转载地址:http://eoao.baihongyu.com/