洛谷 P8674 [蓝桥杯 2018 国 B] 调手表

---

---

[蓝桥杯 2018 国 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$意义如题。

输出格式

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

样例 #1

样例输入 #1

5 3

样例输出 #1

2

提示

【样例解释】

如果时间正确则按 $0$ 次。否则要按的次数和操作系列之间的关系如下

1. +1
2. +1, +1
3. +3
4. +3, +1

【数据约定】

对于 $30\%$ 的数据 $0<k<n\le 5$。

对于 $60\%$ 的数据 $0<k<n\le 100$。

对于 $100\%$ 的数据 $0<k<n\le 10^5$。

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

---

---

题意解析

• 对于手表的某一时刻调到另一时刻最少需要按多少次然后取最大次数。
  • 需要注意的是我们有俩按键+1和+k
  • 拿 $n=10,k=6$ 举例
    
    • 我们先从+0开始这一步需要 $0$ 次操作。
    • 从最少的操作目前是 $0$ 开始往后延伸分别+1和+6。
      • +1那么就是 $0+1=1$也就是说+1操作需要 $1$ 步。
      • +6那么就是 $0+6=6$也就是说+6操作需要 $1$ 步。
    • 以此类推每次都要以最小的那个操作数为源点往后延伸。

---

CODE

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define INF 0x3f3f3f3f 

using namespace std;

typedef pair<int, int> pii;  // 定义一个类型表示一对整数

const int N = 1E5 + 10, M = 2E5 + 10;
int n, k;  // n是点的数量k是每次可以增加的步数
int h[N], e[M], ne[M], w[M],idx;  // h, e, ne用于存储图的信息idx是当前边的编号
int dist[N];  // dist用于存储每个点到起点的最短距离
bool st[N];  // st用于标记每个点是否已经被访问过
priority_queue<pii, vector<pii>, greater<pii>> heap;  // 定义一个小顶堆用于存储待处理的点
int maxnum = 0;  // 用于存储最大的距离

void add(int ver, int x){
    int des = (ver + x) % n;  // 计算下一个点的编号
    
    // 如果通过这条边可以使得起点到终点的距离更短就更新距离
    if(dist[des] > dist[ver] + 1){
        dist[des] = dist[ver] + 1;
        heap.push({dist[des], des});  // 将终点加入堆中
    }
}

int dijkstra(){
    memset(dist, INF, sizeof dist);  // 初始化所有点到起点的距离为无穷大
    dist[0] = 0;  // 起点到自己的距离为0
    
    heap.push({0, 0});  // 将起点加入堆中
    
    while(heap.size()){
        auto t = heap.top();  // 取出堆顶元素
        heap.pop();
        
        int ver = t.second, dis = t.first;  // ver是点的编号dis是起点到该点的距离
        if(st[ver]) continue;  // 如果该点已经被访问过就跳过
        
        st[ver] = true;  // 标记该点已经被访问过
        
        maxnum = max(maxnum, dis);  // 更新最大的距离
        
        add(ver, 1), add(ver, k);  // 尝试向前走一步和向前走k步
    }
    
    return maxnum;  // 返回最大的距离
}

int main()
{
    cin >> n >> k;  // 输入点的数量和每次可以增加的步数
    
    cout << dijkstra() << endl;  // 输出最大的距离
}

---

分析一下复杂度

本题没有m即边数而每次操作执行两个情况所以说边数 $m=2$ 是个常量那么除了朴素 $Dijkstra(O(n^2))$ 其他单源最短路应该都可以做。