1 条题解

  • 0
    @ 2026-5-2 10:20:25

    题目意思:

    (1,1)(1,1) 开始,每一次可以向上、向右或向右上最多跳 kk 格,问:至少要跳几次才能到 (n,m)(n,m)

    大体思路:

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

    • 向右上跳,nnmm 会同时加上跳跃距离,因而可以得出跳跃的次数为:(min(n,m)+k-1)/k
    • 向上或右跳,很好理解,由于无法向右上跳了,说明应该到了第 nn 行,第 nn 列或第 mm 行,第 mm 列了,剩下的跳跃次数,就是 (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;
    }
    
    • 1

    信息

    ID
    9561
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者