自动搬运

查看原文

来自洛谷，原作者为

	jiangyunuo 没有任何期待没有意外

搬运于2025-08-24 23:09:35，当前版本为作者最后更新于2025-02-10 14:12:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目意思：

从 $(1,1)$ 开始，每一次可以向上、向右或向右上最多跳 $k$ 格，问：至少要跳几次才能到 $(n,m)$？

大体思路：

显然，向右上跳肯定是最优的，所以我们最先考虑，直到无法向右上跳就考虑向右或向上。

• 向右上跳，$n$ 和 $m$ 会同时加上跳跃距离，因而可以得出跳跃的次数为：(min(n,m)+k-1)/k。
• 向上或右跳，很好理解，由于无法向右上跳了，说明应该到了第 $n$ 行，第 $n$ 列或第 $m$ 行，第 $m$ 列了，剩下的跳跃次数，就是 (max(n,m)-min(n,m)+k-1)/k。
• 于是把他们相加即可得到答案。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	n--;m--;  //由于从 (1,1)，开始，需要让 n,m 分别减 1，从而实现从 (0,0)，开始跳的效果，才符合前面的公式。
	cout<<(min(n,m)+k-1)/k+(max(n,m)-min(n,m)+k-1)/k;
	return 0;
}