P11697 [ROIR 2025] 二维蚱蜢 (Day 1) 题解

wangzhechun · 2025-02-10 09:12:14 · 题解

(づ｡◕‿‿◕｡)づP11697 [ROIR 2025] 二维蚱蜢 (Day 1) 题解

题目传送门

博客查看更佳

起点是 (1,1)，终点是 (n,m)，所以我们要向上走 n-1 格，向右走 m-1 格。这里我们假设 n \ge m（若不满足则 swap(n,m)，答案不变）。显然，斜着走比直着走更划算。所以我们可以先向右上方走 m-1 格，需要 \frac {(m-1)+k-1} k 次（向上取整，所以加 k-1）。再向上走 n-m 格，需要 \frac {(n-m)+k-1} k 次。相加即是答案。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;

    if (n < m)
        swap(n, m);

    n--;
    m--;
    ans += (m + k - 1) / k;
    ans += (n - m + k - 1) / k;
    cout << ans;
    return 0;
}   //code by wangzhechun

然后我们就可以完美的AC这道题啦~(≧▽≦)/~。