调手表 BFS

调手表题目描述小明买了块高端大气上档次的电子手表他正准备调时间呢。在 M78 星云时间的计量单位和地球上不同M78 星云的一个小时有n nn分钟。大家都知道手表只有一个按钮可以把当前的数加一。在调分钟的时候如果当前显示的数是0 00那么按一下按钮就会变成1 11再按一次变成2 22。如果当前的数是n − 1 n-1n−1按一次后会变成0 00。作为强迫症患者小明一定要把手表的时间调对。如果手表上的时间比当前时间多1 11则要按n − 1 n-1n−1次加一按钮才能调回正确时间。小明想如果手表可以再添加一个按钮表示把当前的数加k kk该多好啊…他想知道如果有了这个 k kk按钮按照最优策略按键从任意一个分钟数调到另外任意一个分钟数最多要按多少次。注意按 k kk按钮时如果加k kk后数字超过n − 1 n-1n−1则会对n nn取模。比如n 10 , k 6 n10, k6n10,k6的时候假设当前时间是0 00连按2 22次 k kk按钮则调为2 22。输入描述一行两个整数n , k n, kn,k0 k n ≤ 10 5 0 k n \leq 10^50kn≤105意义如题。输出描述输出一行一个整数表示按照最优策略按键从一个时间调到另一个时间最多要按多少次。输入输出样例示例输入5 3输出2样例解释如果时间正确则按0 00次。否则要按的次数和操作系列之间的关系如下1 11 1 112 22 1 , 1 1, 11,13 33 3 334 44 3 , 1 3, 13,1运行限制最大运行时间1 11s最大运行内存:256 256256M题目分析题目可以转化为在模 n 的环上从 0 出发用 1 和 k 两种操作求最远能几步到达某个数把环看成一个图每一次调试1 或者 k代价相同遍历图将模 n 的环看成一个有 n 个节点的图每个节点表示一个余数 0∼n−1。从节点 x 出发可以走到( x 1 ) m o d n (x1)\mod n(x1)modn( x k ) m o d n (xk)\mod n(xk)modn每条边表示一次操作1 或 k代价均为 1这其实是用 BFS 按层遍历图计算最短距离代码#includeiostream#includequeue#includecstringusingnamespacestd;constintN100010;intdist[N];intmain(){intn,k;cinnk;memset(dist,-1,sizeof(dist));queueintq;dist[0]0;q.push(0);while(!q.empty()){intcurq.front();q.pop();// 两种操作1 和 kintnext1(cur1)%n;intnextk(curk)%n;if(dist[next1]-1){dist[next1]dist[cur]1;q.push(next1);}if(dist[nextk]-1){dist[nextk]dist[cur]1;q.push(nextk);}}// 找到最大值intmaxDist0;for(inti0;in;i){maxDistmax(maxDist,dist[i]);}coutmaxDistendl;return0;}