题解

算法思路

这是一个数学构造/贪心问题。k-蚱蜢可以向右、向上或右上方向移动最多 $k$ 格。我们需要从 $(1,1)$ 到 $(n,m)$ 的最少步数。

关键观察：

1. 由于可以沿对角线移动，最优策略是尽量走对角线，因为一次对角线移动相当于同时向右和向上各移动 1 格
2. 如果 $n > m$，交换两者（因为问题是对称的）
3. 计算过程：
   • 先走 $\lfloor \frac{n-1}{k} \rfloor$ 次对角线（每次移动 $k$ 格）
   • 如果还有剩余 $(n-1) \bmod k > 0$，需要额外一步
   • 然后向右移动剩余距离 $\lfloor \frac{m-n}{k} \rfloor$ 次
   • 如果还有剩余 $(m-n) \bmod k > 0$，需要额外一步

算法步骤

1. 如果 $n > m$，交换两者使 $n \leq m$
2. 计算 $(n-1)/k$ 的商和余数
3. 计算 $(m-n)/k$ 的商和余数
4. 总步数 = 两个商的和 + 两个余数是否大于 0 的指示值

复杂度分析

• 时间复杂度：$O(1)$，只有常数次算术运算
• 空间复杂度：$O(1)$，只用了几个变量

算法标签

• 贪心算法
• 数学构造
• 数论
• 最优策略