小明買了塊高端大氣上檔次的電子手表，他正準備調時間呢。在 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 ，意義如題。

輸出格式
一行一個整數。表示：按照最優策略按鍵，從一個時間調到另一個時間最多要按多少次。

樣例輸入：
5 3

樣例輸出：
2

「數據范圍」
對于 30% 的數據 0 < k < n <= 5
對于 60% 的數據 0 < k < n <= 100
對于 100% 的數據 0 < k < n <= 100000

解題思路：
一道很隱蔽的bfs(可能我水平太低)，用bfs，第一次到的次數一定是最少的，把按全部點的次數找出來，然后找最大的。

代碼如下：

#include <iostream> #include <string> #include <queue> using namespace std; const int N = 100010; int a[N]; int n,k; int ans = -1; int bfs() {queue<int>q;q.push(0);a[0] = 0;while(q.size()){int t = q.front();q.pop();if (a[(t+1)%n]==-1) {a[(t+1)%n] = a[t]+1;q.push(((t+1)%n));}if (a[(t+k)%n]==-1){a[(t+k)%n] = a[t]+1;q.push(((t+k)%n));} }for (int i = 0;i<n;i++){ans = max(a[i],ans);}return ans; }int main() {cin>>n>>k;memset(a,-1,sizeof(a));cout<<bfs()<<endl;return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[蓝桥杯][2018年第九届真题]调手表-bfs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。