Flappy Bird 题解

问题分析

小鸟从 $(0,0)$ 出发，要到达 $(X, y)$（任意 $y$）。每次移动：

• 点击：$(x+1, y+1)$
• 不点击：$(x+1, y-1)$

设总点击次数为 $t$，总移动次数为 $X$，则最终位置为：

所以最终高度由点击次数决定：$y = 2t - X$

关键观察

1. 移动约束

在位置 $x$ 时，如果已经点击了 $k$ 次，那么可能的高度范围是：

但实际上更精确的范围是：$y \in [k - (x-k), k + (x-k)] \cap \mathbb{Z}$，即 $y \equiv x \pmod{2}$

2. 障碍约束

在障碍 $x_i$ 处，高度不能 $\leq a_i$ 或 $\geq b_i$，所以安全高度区间是 $(a_i, b_i)$

3. 问题转化

我们需要找到最小的 $t$，使得存在一条从 $(0,0)$ 到 $(X, 2t-X)$ 的路径，避开所有障碍。

算法思路

方法：动态维护可达区间

对于每个障碍位置 $x_i$，维护一个可达的高度区间 $[L_i, R_i]$，表示在 $x_i$ 位置可能达到的高度范围。

从 $x=0$ 开始，初始区间为 $[0,0]$。

对于每个障碍 $x_i$，从前一个障碍 $x_{i-1}$ 转移：

• 经过 $d = x_i - x_{i-1}$ 步移动
• 高度范围会扩展：新区间 = $[L_{i-1} - d, R_{i-1} + d]$
• 与安全区间 $(a_i, b_i)$ 取交集
• 还要满足奇偶性约束：区间内的高度与 $x_i$ 同奇偶性

如果某个障碍处区间为空，则输出 NIE。

最终答案为满足 $2t - X$ 在最终区间内的最小 $t$。

复杂度分析

• 时间复杂度：$O(n)$，每个障碍处理一次
• 空间复杂度：$O(n)$，存储障碍信息

算法正确性

该算法基于以下观察：

1. 小鸟的可达高度区间在每个障碍处会扩展（因为可以选择点击或不点击）
2. 扩展后的区间需要与障碍的安全区间取交集
3. 高度必须与当前位置同奇偶性（因为 $y \equiv x \pmod{2}$）

样例验证

样例1

输入：
4 11
4 1 4
7 -1 2
8 -1 3
9 0 2
输出：5

验证：最终计算得到最小点击次数为5。

样例2

输入：
1 2
1 -1 1
输出：NIE

验证：在第一个障碍处，可达区间变为空，无法通过。

总结

本题通过动态维护可达高度区间，巧妙地避免了显式的动态规划，实现了线性时间复杂度的解决方案。关键在于理解移动的数学约束和障碍的安全区间限制。

最终算法标签： 区间维护 动态规划 数学分析 贪心算法