题目描述


题目分析

从任意一个分钟调到另外任意一个分钟可以看成从 0 调到任意分钟,那么问题转化成以最优策略 +1 或 +k 从 0 调到任意分钟最多要操作多少次,由于是最优策略所以使用广度优先搜索(BFS)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<queue>
using namespace std;
const int N=100000;

int n,k;
int vis[N];
int ans;

void bfs() {
queue<pair<int,int>> q;
q.push(make_pair(0,0));
vis[0]=1;
while(!q.empty()) {
int x=q.front().first,y=q.front().second;
q.pop();
ans=max(ans,y);
int tx=(x+1)%n;
if(!vis[tx]) {
q.push(make_pair(tx,y+1));
vis[tx]=1;
}
tx=(x+k)%n;
if(!vis[tx]) {
q.push(make_pair(tx,y+1));
vis[tx]=1;
}
}
}

int main()
{
cin>>n>>k;
bfs();
cout<<ans<<endl;

return 0;
}