Jumping in the hills跳山题Python代码错误排查

题目规则 #

现有排成一行的N座山丘，从左到右编号为1到N，对于合法的i，第i座山丘高度为Hi。Chef初始位于最左侧的1号山丘，满足以下规则时可进行任意次跳跃（包括0次），需要求其能到达的最右侧山丘编号：

• 仅可从当前i号山丘跳跃到相邻右侧的i+1号山丘（若存在）；
• 相邻山丘高度相同时始终可跳跃；
• 跳向更高山丘时，高度差不得超过U；
• 跳向更低山丘时，高度差不得超过D；
• 最多可使用1次降落伞，使用后可不受D值限制跳向任意更低的相邻山丘。

输入输出要求 #

• 输入第一行为整数T，表示测试用例总数；
• 每个测试用例第一行包含3个空格分隔的整数N、U、D；
• 每个测试用例第二行包含N个空格分隔的整数H1、H2...HN，表示各山丘高度；
• 对每个测试用例，输出单个整数，即可到达的最右侧山丘编号。

约束范围 #

1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ U, D ≤ 1,000,000
1 ≤ Hi ≤ 1,000,000

官方样例 #

输入：

3
5 3 2
2 5 2 6 3
5 2 3
4 4 4 4 4
5 2 7
1 4 3 2 1

输出：

3
5
1

现存问题 #

已有Python实现代码可通过上述官方样例，但提交无法通过全部测试用例。其中一组失败用例如下：

• 输入：

1
5 2 1
3 5 3 4 1

• 代码输出：5
• 预期正确输出：4

原有实现代码：

t=int(input())

for i in range(t):
    n,u,d=map(int,input().split())
    h=[int(k) for k in input().split()]
    steps=0
    check=0
    for l in range(n-1):
        if l==n:
            break
        if h[l]==h[l+1] or h[l+1]-h[l]<=u:
            steps+=1
        
        elif h[l]-h[l+1]>0:
            if h[l]-h[l+1]<=d:
                steps+=1
            elif check==0:
                steps+=1
                check+=1
            else:break
        else:break
    print(steps+1)

错误原因 #

原代码第一个条件判断存在明显逻辑漏洞：h[l]==h[l+1] or h[l+1]-h[l]<=u 没有限定上坡场景。只要是下坡，h[l+1]-h[l]就是负数，必然满足<=u的条件，代码会直接判定跳跃合法，完全跳过下坡的高度差校验、降落伞剩余次数校验逻辑。
以上述失败用例为例，高度序列为[3,5,3,4,1]，U=2，D=1：

1. 从高度5的山丘跳到高度3的山丘时，下坡差为2，超过D=1的限制，会消耗唯一一次降落伞；
2. 走到高度4的第4座山丘后，下一个山丘高度为1，下坡差为3，既超过D值限制，也没有剩余降落伞可用，按规则无法跳跃，最远只能到第4座山丘；
3. 但原代码判断该段跳跃时，h[4]-h[3] = -3 <= 2，直接判定跳跃合法，错误累加步数，最终输出错误结果5。

修复方案 #

拆分判断逻辑，严格区分等高、上坡、下坡三种场景：

• 等高场景直接允许跳跃；
• 上坡场景单独校验高度差不超过U；
• 下坡场景先校验高度差是否在D允许范围内，超过的话再检查是否有可用降落伞，没有则直接停止。

修复后可运行代码：

t = int(input())
for _ in range(t):
    n, u, d = map(int, input().split())
    h = list(map(int, input().split()))
    pos = 0
    parachute_used = 0
    for i in range(n-1):
        diff = h[i+1] - h[i]
        if diff == 0:
            pos += 1
        elif diff > 0:
            if diff <= u:
                pos += 1
            else:
                break
        else:
            down_diff = -diff
            if down_diff <= d:
                pos += 1
            else:
                if not parachute_used:
                    parachute_used = 1
                    pos += 1
                else:
                    break
    print(pos + 1)

修复后代码运行失败用例输出为4，符合预期，可覆盖全部测试场景。

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