[蓝桥杯2018决赛]调手表

链接： http://oj.ecustacm.cn/problem.php?id=1393

1、按照最优策略按键（最坏需要调n-1次），从任意一个分钟数调到另外任意一个分钟数最多要按多少次(*)。 

2、注意，按 +k 按钮时，如果加k后数字超过n-1,则会对n取模。

宽搜是参考其他兄弟的博客。。。。。

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int n,k;
int cur,ans;
int mem[100005];

// 深搜 ，只能得了40分，提示超时....
void dfs(int end, int step, int cur) {
    if (cur == end) {
        if (step > ans) {
            if (ans < step) ans = step;
        }
        return;
    }
    // 按最优决策
    if (end-cur >= k) {
        dfs(end, step+1, (cur+k)%n);
    } else {
        dfs(end, step+1, (cur+1)%n);
    }
}

// 宽搜，满分
void bfs()  {
    queue<int> q;
    // 初始化从0点开始
    q.push(0); 
    mem[0] = 0;
    
    while(!q.empty()) {
        int p = q.front();
        q.pop();
        if (mem[(p+1)%n] == -1) {
            mem[(p+1)%n] = mem[p] + 1;
            q.push((p+1)%n);
        }
        if (mem[(p+k)%n] == -1) {
            mem[(p+k)%n] = mem[p] + 1;
            q.push((p+k)%n);
        }
    }
}

int main() {

    while(~scanf("%d%d", &n, &k)) {
        ans = 0;
        memset(mem, -1, sizeof mem);
//        for (int i = 0; i < n; i++) {
//            dfs(i, 0, 0);
//        }
        bfs();
        for (int i = 0; i < n; i++) {
            if (mem[i] > ans) ans = mem[i];
//            printf("%d ", mem[i]);
        }
        cout << ans << endl;    
    }
    return 0;
}

。。。。。。。。。。。。。。。