自动搬运

查看原文

来自洛谷，原作者为

	Nuyoah_awa 事实证明，你没让我失望。

搬运于2025-08-24 22:41:20，当前版本为作者最后更新于2023-04-02 21:37:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

小明有一块电子表，准备调时间，M78 星云上一个小时 $n$ 分钟，小明每次可以往前调 $1$ 分钟或 $k$ 分钟，求按照最优策略按键，从一个时间调到另一个时间最多要按多少次。

题目分析

小明从第 $a$ 分钟调到第 $b$ 分钟，假设 $a$ 与 $b$ 相差 $c$ 分钟（$c < n$），我们可以把从第 $a$ 分钟调到第 $b$ 分钟看为从第 $0$ 分钟调到第 $c$ 分钟，这样题意就简化为了从 $0$ 开始，调到任意时间最少按多少次。

我们可以把这道题视为一个图论题，我们将每个数 $u$ 向 $u + k$ 和 $u + 1$ 连边，问题就转化为了求 $0$ 号节点到每个节点最短路的最大值，然后这道题就可以转换为 $\operatorname{bfs}$ 求解了。

由于每个点到 $0$ 的距离最大为 $n - 1$，就说明即使每回往后调 $1$，调 $n - 1$ 次就可以调到所有时间了，所以时间复杂度是 $\mathcal O(n)$ 的。

code

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1e5 + 5;
int n, k, t[N], cnt[N], x, y1, y2, ans;
queue <int> q;

int main()
{
	scanf("%d %d", &n, &k);
	cnt[0] = true;
	q.push(0);
	while(!q.empty())
	{
		x = q.front();
		q.pop();
		ans = max(ans, t[x]);
		y1 = (x + k) % n, y2 = (x + 1) % n;
		if(!cnt[y1])
		{
			t[y1] = t[x] + 1, cnt[y1] = true;
			q.push(y1);
		}
		if(!cnt[y2])
		{
			t[y2] = t[x] + 1, cnt[y2] = true;
			q.push(y2);
		}
	}
	printf("%d", ans);
	return 0;
}