python-调手表

解题思路:

开始使用动态规划做的，超时了，只有55分。

下面代码是参照的别人的思路。算是留个参考吧。

也简单说一下自己的理解吧。

建立一个大小为n的数组A，其中A[i],代表的是从任意一点到点i的最小值。

A初始化全部为-1，代表所有的点都还未到达过。

用广度搜索，下面的广度搜索算法没有采用递归，而是用队列实现的。

先遍历步长为1的，再遍历步长为k的。先到达的点一定是次数最小的，将先到达的点更新完成之后，再利用它们去更新之后到达的点。

然后输出A中的最大值。

注意事项:

参考代码:

def bfs(A,n,k):    
     
    Q = []    
    Q.append(0)    
    A[0] = 0    
     
    while len(Q):    
        t = Q.pop(0)    
     
        if A[(t+1)%n] == -1:    
            A[(t+1)%n] = A[t] + 1    
            Q.append((t+1)%n)    
     
        if A[(t+k)%n] == -1:    
            A[(t+k)%n] = A[t] + 1    
            Q.append((t+k)%n)    
         
    return max(A)    
     
if __name__ == '__main__':     
    n,k = map(int,input().strip().split())    
    A = [-1 for i in range(n)]    
    print(bfs(A,n,k))