跳跃过桥（Jump Game）

跳跃过桥

题目描述

有 n 个方块组成的桥，每个方块有价值 a_i。起点为 0，终点为 n+1。跳跃能力为 k，每次可跳 [X+1, X+k] 范围内的任意位置。求过桥代价的最小值（代价 = 经过方块的最大价值）。

思路分析

如何思考这个问题？

1. 代价的定义：代价是路径上所有方块价值的最大值

2. 状态的表示：设 dp[i] = 到达位置 i 的最小代价（即路径上最大值的最小可能）

3. 状态转移：

   • 从位置 j 可以跳到 i，当 j ∈ [i-k, i-1]
   • dp[i] = min( max(dp[j], a[i]) ) for j ∈ [i-k, i-1]
   • 解释：选择从某个 j 跳过来，代价是 max(到达 j 的代价, i 位置的价值)

4. 优化方向：

   • 直接 DP 复杂度 O(nk)
   • 注意到转移只需要窗口 [i-k, i-1] 内的最小 dp 值
   • → 使用单调队列在 O(1) 时间内获取最小值

为什么单调队列可行？

单调队列的核心思想：

• 队列按 dp 值单调递增存储
• 队首 q[0] 始终是当前窗口内的最小 dp 值
• 队尾插入时，移除所有 dp 值更大的元素（它们永远不是最优的）

这样就能在 O(1) 时间获取窗口最小值，整体 O(n)。

解题思路

方法一：二分搜索 + 贪心（更简洁）

观察题目特点：

• 答案单调性：如果代价 X 可以过桥，那么更大的代价 Y 也一定可以过桥
• 因此可以使用二分搜索，二分答案 + 贪心验证

方法二：滑动窗口 + 单调队列（更高效）

直接 DP 求解：

• dp[i] = min( max(dp[j], a[i]) ) for j ∈ [i-k, i-1]
• 使用单调队列在 O(1) 时间内获取窗口最小值
• 整体时间 O(n)，空间 O(k)

代码实现

方法一：二分搜索

def first_true(lo, hi, check):
    """查找第一个满足 check(x) 为 True 的 x"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_reach(target):
    """检查是否能通过跳跃长度 k 到达终点"""
    farthest = k
    for i in range(1, n + 1):
        if a[i] <= target and i <= farthest:
            farthest = max(farthest, i + k)
    return farthest >= n + 1

for _ in range(t):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split())) + [0]  # 添加起点和终点
    result = first_true(min(a), max(a), can_reach)
    print(result)

方法二：单调队列（更高效）

from collections import deque

t = int(input())

def solve_one(n, k, a):
    q = deque()
    q.append((0, 0))
    cost = 0

    for i in range(1, n + 2):
        while q and q[0][0] < i - k:
            q.popleft()
        if q:
            cost = max(q[0][1], a[i])
            while q and q[-1][1] >= cost:
                q.pop()
            q.append((i, cost))
    return cost

    
for _ in range(t):
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split())) + [0]
    print(solve_one(n, k, a))

核心逻辑详解

单调队列工作流程

以 n=5, k=2, a=[1,2,3,4,5] 为例：

i	窗口 [i-k, i-1]	队列状态	min_dp	dp[i]
1	[max(0, -1), 0] = [0,0]	(0,0)	0	max(0,1)=1
2	[0,1]	(0,0),(1,1)	0	max(0,2)=2
3	[1,2]	(1,1),(2,2)	1	max(1,3)=3
4	[2,3]	(2,2),(3,3)	2	max(2,4)=4
5	[3,4]	(3,3),(4,4)	3	max(3,5)=5
6	[4,5]	(4,4),(5,5)	4	max(4,0)=4

最终 dp[6]=4，即为答案。

为什么队首是最小值？

队列维护两个不变量：

1. 位置有效性：队首位置始终在窗口 [i-k, i-1] 内
2. 单调性：队列按 dp 值递增排列

因此队首 q[0][1] 永远是当前窗口内的最小 dp 值。

为什么可以移除 dp 值更大的元素？

当插入新位置 i（dp[i]=x）时：

• 队列中已有的元素 j（dp[j] >= x）在位置 i 之后仍然是可达的
• 但它们的 dp 值更大，所以对于任何后续位置，j 都不可能比 i 更优
• 因此可以安全移除

复杂度分析

方法一：二分搜索

• 时间复杂度：O(n log V)，V 为价值范围
• 空间复杂度：O(n)

方法二：单调队列

• 时间复杂度：O(n)，每个位置最多入队和出队一次
• 空间复杂度：O(k)，队列最多存储 k 个元素