P8674题解

Nuyoah_awa · 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;
}