InterviewBit步数游戏超时求助：求无限数轴到达目标点的最少步数

原代码的问题 #

你的代码超时的核心原因有两个：

1. 逻辑漏洞导致死循环：当B+i恰好等于A时，代码里的两个if分支都不会执行，B、i、count都不会更新，while(A!=B)会无限循环。
2. 贪心策略错误：局部的“靠近目标”选择不一定能导向全局最优解，反而可能绕远路，甚至永远无法到达目标点。

正确思路 #

由于数轴正负对称，先将目标值A取绝对值，只需要处理正数情况即可：

1. 先找到最小的n，使得前n项和S = n*(n+1)/2大于等于A。
2. 计算差值d = S - A：
   • 如果d是偶数：直接返回n，因为我们可以把第d/2步的方向反转（原本加d/2，现在减d/2，总和会减少d，刚好等于A）。
   • 如果d是奇数：需要继续累加下一步的步数，直到差值变为偶数：
     • 若n+1是奇数，加n+1后新的差值d + (n+1)是偶数，返回n+1。
     • 若n+1是偶数，加n+1后差值还是奇数，再加n+2（奇数），差值变为偶数，返回n+2。

修正后的代码 #

int solve(int A) {
    A = abs(A);
    int n = 0;
    int sum = 0;
    while (sum < A) {
        n++;
        sum += n;
    }
    int diff = sum - A;
    while (diff % 2 != 0) {
        n++;
        sum += n;
        diff = sum - A;
    }
    return n;
}

代码解释 #

1. 取绝对值：因为正负方向对称，处理正数即可简化逻辑。
2. 累加求和找最小n：找到第一个前n项和大于等于A的n。
3. 调整差值为偶数：如果当前差值是奇数，继续累加步数直到差值为偶数，此时的n就是最少移动次数。

内容的提问来源于stack exchange，提问作者driver