题解：P11697 [ROIR 2025] 二维蚱蜢

jiangyunuo · 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;
}