题干信息解读

跳跳虎从数轴上的点 $n$ 出发，要跳到点 $m$。跳跃规则为：上一次跳跃距离为 $x$ 时，本次跳跃距离需在 $\begin{bmatrix} x−1,x+1 \end{bmatrix}$ 范围内，且首次和最后一次跳跃的距离必须为 1。要求计算最少的跳跃次数，使跳跳虎从 $n$ 到达 $m$。

整体做题思路

1.简化问题：首先计算起点与终点的直线距离 $d=∣m−n∣$ 。若 $d=0$ ，无需跳跃，次数为 0。
2.分析跳跃序列：跳跃距离序列需满足：首项和末项为 1，相邻项差值不超过 1，且所有项之和为 $d$ 。为求最少次数，序列应先递增至最大值再递减（最大化每次跳跃距离）。
3.寻找最小次数：通过枚举可能的跳跃次数 $k$ ，计算该次数下最大可能的总距离 $S(k)$ 。若$S(k)≥d$ 且 $d≥k$ ，则 $k$ 为可行解（可通过调整中间跳跃距离使总距离恰好为 $d$ ）。

难点和注意事项

1.跳跃序列的最大值计算：

• 当 $k$ 为奇数时，最大总距离 $S(k)=t^2$ （其中 $t=(k+1)/2$ ）。
• 当 $k$ 为偶数时，最大总距离 $S(k)=t×(t+1)$（其中 $t=k/2$ ）。

2.可行性判断：需满足 $S(k)≥d$（总距离足够）且 $d≥k$（可通过调整中间跳跃距离使总距离减少到 $d$ ）。
3.边界情况处理：如 $d=1$ 时，仅需 1 次跳跃（距离 1）。

AC代码（如有雷同，纯属巧合）

#include <iostream>
#include <cmath>
using namespace std;

// 计算k次跳跃的最大可能总距离
long long computeMaxSum(int k) {
    if (k % 2 == 1) {
        // 奇数k：序列为1,2,...,t-1,t,t-1,...,2,1（t=(k+1)/2）
        long long t = (k + 1) / 2;
        return t * t;
    } else {
        // 偶数k：序列为1,2,...,t,t,...,2,1（t=k/2）
        long long t = k / 2;
        return t * (t + 1);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n, m;
        cin >> n >> m;
        long long d = abs(m - n);
        
        if (d == 0) {
            cout << 0 << endl;
            continue;
        }
        
        // 寻找最小的k满足条件
        int k = 1;
        while (true) {
            long long maxSum = computeMaxSum(k);
            // 条件：最大总距离 >= d，且d >= k（确保可调整到d）
            if (maxSum >= d && d >= k) {
                cout << k << endl;
                break;
            }
            k++;
        }
    }
    return 0;
}

难点和注意事项解析

• 距离计算：通过绝对值 $d=∣m−n∣$ 简化问题，忽略方向仅关注距离。
• 最大总距离公式：根据跳跃次数 $k$ 的奇偶性，推导出最大可能的总距离（递增后递减的序列总和），确保以最少次数覆盖距离 $d$ 。
• 可行性条件：$S(k)≥d$ 保证总距离足够，$d≥k$ 保证可通过减少中间跳跃距离调整到恰好 $d$ （中间项可减少的总量足够）。

时间与空间复杂度

• 时间复杂度：对于每个测试用例，枚举的跳跃次数 $k$ 与 $\sqrt{d}$ 成正比（因最大总距离 $S(k)$ 随 $k$ 平方级增长）。当 $d≤10^{10}$ 时，$k$ 最大约为 $2×10^5$，配合 $t≤100$，总运算量可接受。
• 空间复杂度：$O(1)$，仅使用常数个变量存储距离和中间结果。

该方案通过数学分析跳跃序列的规律，高效枚举并验证最少跳跃次数，确保在大规模输入下仍能快速求解。