樱花树小猫跳跃问题 题解

算法标签

数学计算、枚举法、贪心策略、构造性算法

题目分析

小猫需从初始位置 (x, y) 跳跃到目标位置（树1或树n，高度1或h），每次跳跃需同时满足两个核心约束：

1. 树位置：每次固定向左/右移动 a 棵树，需整数次跳跃才能到达目标树。
2. 高度：每次固定上升/下降 b，需整数次跳跃才能到达目标高度。 关键逻辑：总跳跃次数需同时覆盖树位置和高度的到达需求，且两者奇偶性一致（多跳次数需为偶数，可通过“跳出去再跳回来”调整，不改变最终树位置）。

核心思路

1. 目标拆解：共4种有效目标组合（树1+高度1、树1+高度h、树n+高度1、树n+高度h），需逐一验证可行性。
2. 次数计算：对每种组合，分别计算“到达目标树的最小跳跃次数”（树次数）和“到达目标高度的最小跳跃次数”（高度次数）。
3. 可行性验证：树次数和高度次数需均为有限值（可到达），且奇偶性一致（确保总次数能同时满足双需求）。
4. 最优解筛选：可行组合的总跳跃次数为 max(树次数, 高度次数)（需覆盖两者最小需求），取所有可行值中的最小值。

算法步骤

1. 计算4个关键次数（不可达时设为无穷大 0x7FFFFFFFFFFFFFFF）：
   • 树次数 p：从 x 到树1的最小次数 → (x-1) % a == 0 时为 (x-1)/a，否则不可达。
   • 树次数 q：从 x 到树n的最小次数 → (n-x) % a == 0 时为 (n-x)/a，否则不可达。
   • 高度次数 r：从 y 到高度1的最小次数 → (y-1) % b == 0 时为 (y-1)/b，否则不可达。
   • 高度次数 s：从 y 到高度h的最小次数 → (h-y) % b == 0 时为 (h-y)/b，否则不可达。
2. 枚举4种目标组合，验证可行性：
   • 组合1（树1+高度1）：p 和 r 均有限，且奇偶性一致 → 总次数 max(p, r)。
   • 组合2（树1+高度h）：p 和 s 均有限，且奇偶性一致 → 总次数 max(p, s)。
   • 组合3（树n+高度1）：q 和 r 均有限，且奇偶性一致 → 总次数 max(q, r)。
   • 组合4（树n+高度h）：q 和 s 均有限，且奇偶性一致 → 总次数 max(q, s)。
3. 确定答案：筛选所有可行组合的总次数，取最小值；若无可行组合，输出 -1。

代码解析

#include <cstdio>
#include <algorithm>
using namespace std;

int T;
long long n, h, x, y, a, b;
long long p, q, r, s, ans;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld%lld%lld%lld", &n, &h, &x, &y, &a, &b);
        
        // 计算到达树1的最小跳跃次数（不可达设为无穷大）
        p = (x - 1) % a == 0 ? (x - 1) / a : 0x7FFFFFFFFFFFFFFF;
        // 计算到达树n的最小跳跃次数（不可达设为无穷大）
        q = (n - x) % a == 0 ? (n - x) / a : 0x7FFFFFFFFFFFFFFF;
        // 计算到达高度1的最小跳跃次数（不可达设为无穷大）
        r = (y - 1) % b == 0 ? (y - 1) / b : 0x7FFFFFFFFFFFFFFF;
        // 计算到达高度h的最小跳跃次数（不可达设为无穷大）
        s = (h - y) % b == 0 ? (h - y) / b : 0x7FFFFFFFFFFFFFFF;
        
        ans = 0x7FFFFFFFFFFFFFFF; // 初始化答案为无穷大
        
        // 验证4种目标组合，更新最小总次数
        if ((p & 1) == (r & 1)) ans = min(ans, max(p, r));
        if ((p & 1) == (s & 1)) ans = min(ans, max(p, s));
        if ((q & 1) == (r & 1)) ans = min(ans, max(q, r));
        if ((q & 1) == (s & 1)) ans = min(ans, max(q, s));
        
        // 无可行组合时输出-1
        if (ans == 0x7FFFFFFFFFFFFFFF) ans = -1;
        printf("%lld\n", ans);
    }
    return 0;
}

关键代码细节

• 无穷大设置：0x7FFFFFFFFFFFFFFF 是64位整数最大值，用于标记“不可达”状态，避免与有效次数冲突。
• 奇偶性判断：(p & 1) == (r & 1) 等价于 p % 2 == r % 2，高效判断奇偶性是否一致。
• 总次数计算：max(p, r) 是满足双需求的最小总次数——次数需同时覆盖树和高度的最小跳跃需求，多跳的偶数次可通过“往返跳跃”调整。

复杂度分析

• 时间复杂度：O(1) 每组测试数据。仅需固定4次组合枚举和基础算术运算，与输入规模（即使 n, h 达 10^15）无关。
• 空间复杂度：O(1) 仅使用常数个变量存储中间结果，无额外空间开销。