Moe's CF Life

Appearance

Freya 小青蛙的跳跃之旅，喵~ | Codeforces 2009C 题解 ​

主人，你好喵~ 今天我们来帮助一只叫做 Freya 的可爱小青蛙回家吧！这道题看起来有点绕，但只要我们一步一步地分析，就会发现其实很简单哦，就像猫猫追着毛线球一样，抓住线头就好啦！

题目大意 ​

有一只叫 Freya 的小青蛙，她现在在二维平面的原点 (0,0)，想要跳到目标点 (x,y) 去。

她的跳跃规则是这样哒：

  1. 跳跃距离：每一次跳跃，她可以向前跳跃整数距离 d，其中 0 <= d <= k。k 是每次跳跃距离的上限。
  2. 跳跃方向：她的朝向是交替变化的。
    • 一开始，她朝向 x 轴正方向。
    • 第一次跳跃后，她会转向 y 轴正方向。
    • 第二次跳跃后，她又会转回 x 轴正方向。
    • ...以此类推，方向在 x, y, x, y, ... 之间来回切换。

我们的任务是，计算 Freya 小青蛙最少需要跳跃多少次，才能正好到达 (x,y) 点呢？

举个栗子，如果目标是 (9,11)，k=3。

  • 第1跳 (x方向): 跳2 -> (2,0)
  • 第2跳 (y方向): 跳2 -> (2,2)
  • 第3跳 (x方向): 跳1 -> (3,2)
  • 第4跳 (y方向): 跳3 -> (3,5)
  • ... 我们需要找到一个最优的跳跃序列，使得总跳跃次数最少。

解题思路 ​

这道题的关键在于把复杂的跳跃过程拆解开来分析，喵~ 我们可以分开考虑 x 方向和 y 方向的移动需求。

1. 分别计算 x 和 y 方向需要多少次跳跃 ​

  • 对于 x 方向： 为了到达坐标 x，我们需要在 x 方向上总共移动 x 的距离。因为每一次在 x 方向上的跳跃最多只能移动 k，那么为了凑够 x 的距离，最少需要多少次 x方向的跳跃 呢？ 这其实就是一个向上取整的问题，喵~ 比如 x=9, k=3，需要 9/3 = 3 次。如果 x=10, k=3，需要 ceil(10/3) = 4 次。 所以，x 方向最少需要 ceil(x/k) 次跳跃。在整数计算中，ceil(a/b) 可以写成 (a + b - 1) / b。我们把这个值记为 req_x。

  • 对于 y 方向： 同理，y 方向最少需要 ceil(y/k) 次跳跃。我们记为 req_y。

2. 将总跳跃次数和分方向的跳跃次数联系起来 ​

现在我们知道了最少需要 req_x 次 x 方向的跳跃和 req_y 次 y 方向的跳跃。那么，这需要多少次 总跳跃 呢？

我们来看看总跳跃次数 m 和分方向跳跃次数的关系：

  • 第1跳：x 方向
  • 第2跳：y 方向
  • 第3跳：x 方向
  • 第4跳：y 方向
  • ...

可以发现：

  • 在 m 次总跳跃中，x 方向的跳跃次数是第 1, 3, 5, ... 次。总共有 ceil(m/2) 次，也就是 (m+1)/2 次。
  • 在 m 次总跳跃中，y 方向的跳跃次数是第 2, 4, 6, ... 次。总共有 floor(m/2) 次，也就是 m/2 次。
3. 建立不等式并求解 ​

为了让小青蛙成功到达目的地，我们需要的总跳跃次数 m 必须同时满足以下两个条件：

  1. 提供的 x 方向跳跃次数，要足够我们完成 req_x 次的移动需求。 (m+1)/2 >= req_x
  2. 提供的 y 方向跳跃次数，要足够我们完成 req_y 次的移动需求。 m/2 >= req_y

现在我们来解这两个关于 m 的不等式，喵~

  1. 从 (m+1)/2 >= req_x，两边乘以 2，得到 m+1 >= 2 * req_x，所以 m >= 2 * req_x - 1。
  2. 从 m/2 >= req_y，两边乘以 2，得到 m >= 2 * req_y。

m 必须同时满足这两个条件，也就是说，m 必须大于等于 2 * req_x - 1，并且也要大于等于 2 * req_y。为了找到最小的 m，我们只需要取这两个下界中的较大值就可以啦！

所以，最终的答案就是 max(2 * req_x - 1, 2 * req_y)。

是不是一下子就清晰了呀，喵~

题解代码 ​

这是 C++ 的实现代码，我已经加上了可爱的注释哦~

cpp
#include <iostream>
#include <algorithm>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    long long x, y, k;
    std::cin >> x >> y >> k;

    // 为了到达坐标 x，我们需要在 x 方向上累计移动 x 的距离。
    // 每次跳跃最多 k，所以 x 方向最少需要的跳跃次数是 ceil(x/k)。
    // 对于非负整数 x 和正整数 k，ceil(x/k) 可以用 (x + k - 1) / k 来计算，这样可以避免浮点数误差，很棒棒！
    long long req_x = (x + k - 1) / k;

    // y 方向也是同理的啦~
    long long req_y = (y + k - 1) / k;

    // 假设总共跳了 m 次。
    // 第1、3、5... 次是 x 方向，总共 (m+1)/2 次。
    // 第2、4、6... 次是 y 方向，总共 m/2 次。
    //
    // 我们需要找到最小的 m，满足：
    // 1. (m + 1) / 2 >= req_x  =>  m >= 2 * req_x - 1
    // 2. m / 2 >= req_y      =>  m >= 2 * req_y
    //
    // m 必须同时满足这两个条件，所以 m 必须大于等于它们中的最大值。
    // 这就是我们推导出的最终公式啦，喵~
    long long ans = std::max(2 * req_x - 1, 2 * req_y);

    std::cout << ans << std::endl;
}

int main() {
    // 这两行是为了加速输入输出，在处理大量数据时很有用哦。
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍 ​

这道题虽然是 C 题，但涉及到的知识点非常实用，值得我们好好掌握一下，喵~

  1. 整数除法与向上取整 (Ceiling Function) 在编程竞赛中，我们经常需要计算 ceil(a/b)，也就是 a/b 的向上取整。如果直接使用 ceil((double)a / b)，可能会因为浮点数精度问题而出错。对于正整数 a 和 b，有一个非常稳定和常用的整数计算技巧： ceil(a/b) = (a + b - 1) / b 这个公式的原理是，先把 a 加上 b-1，这样任何原本不能整除的数，在加上这个偏移量之后，再进行整数除法（向下取整）时，结果就会加一，正好达到了向上取整的效果。而原本就能整除的数，加上 b-1 后也不会越过下一个 b 的倍数，所以结果不变。 例如：ceil(10/3)=4 -> (10+3-1)/3 = 12/3 = 4。 ceil(9/3)=3 -> (9+3-1)/3 = 11/3 = 3。

  2. 问题分解 (Problem Decomposition) 这是一个非常核心的解题思想。面对一个看起来有点复杂的问题（比如带方向交替的跳跃），一个有效的策略是将其分解成更小、更简单的子问题。在这道题里，我们把“到达(x,y)”这个目标，分解成了“满足x方向的移动需求”和“满足y方向的移动需求”两个独立的子问题。先分别求出每个子问题的最小需求（req_x, req_y），然后再把它们组合起来，找到满足所有需求的最终解。

  3. 下界分析 (Lower Bound Analysis) 我们的解法是通过寻找答案的必要条件来确定答案的。我们推导出了 m 必须满足的两个不等式，这两个不等式给出了 m 的两个“下界”。为了满足所有条件，m 必须大于等于所有的下界，因此最小的 m 就是所有下界中的最大值。这是一种在构造性问题和最优化问题中非常常见且强大的思维方式。

希望这篇题解能帮到主人哦！如果还有其他问题，随时可以再来问我，喵~

Released under the MIT License.

Copyright © 2024-present Moe