问题理解

我们有一个长度为 $n$ 的走廊，每扇门要么开（$0$）要么关（$1$）。Yousef 从第 $1$ 扇门开始，必须按顺序通过所有门到达出口。他有一个特殊按钮，最多使用一次，按下后所有关着的门会打开并持续 $x$ 秒。

关键观察

1. 最优策略：当遇到关着的门时才按按钮，而不是在开着的门时按。因为提前按只会浪费按钮的有效时间。

2. 核心问题：我们需要找到所有关着的门中，最左边和最右边的位置。因为按钮一旦按下，所有关着的门都会打开，但持续时间为 $x$ 秒。

3. 区间长度：令：

   • $l$ = 最左边关着的门的位置（索引从 $0$ 开始）
   • $r$ = 最右边关着的门的位置（索引从 $0$ 开始）

   那么需要按钮效果覆盖的区间长度 = $r - l + 1$（表示从第 $l$ 扇门到第 $r$ 扇门共有多少扇门）。

4. 时间需求：

   • 每通过一扇门需要 $1$ 秒
   • 从第 $l$ 扇门到第 $r$ 扇门，需要连续通过 $r - l + 1$ 扇门
   • 因此按钮效果持续时间 $x$ 必须 $\ge$ $r - l + 1$

为什么这样是正确的？

因为：

• 所有关着的门都位于区间 $[l, r]$ 内
• 开着的门不需要按钮帮助
• 如果按钮持续时间足够覆盖从第一个关着的门到最后一个关着的门，那么当你在第 $l$ 扇门按下按钮时，直到你通过第 $r$ 扇门，所有关着的门都是打开的
• 反之，如果 $x < r - l + 1$，则在你到达第 $r$ 扇门之前，按钮效果就已经结束，导致无法通过某个关着的门

算法步骤

1. 初始化 $l = +\infty$（或一个很大的数，如 $10^5$），$r = -1$
2. 遍历所有 $n$ 扇门（索引从 $0$ 到 $n-1$）：
   • 如果当前门是关着的（$a_i = 1$）：
     • 更新 $l = \min(l, i)$
     • 更新 $r = \max(r, i)$
3. 判断：如果 $x \ge r - l + 1$，输出 "YES"，否则输出 "NO"

时间复杂度

• 每个测试用例：$O(n)$
• 总时间复杂度：$O(\sum n) \le O(1000 \times 10) = O(10000)$

空间复杂度

• $O(1)$

示例验证

示例 1

$n=4, x=2$，状态：$0,1,1,0$

• $l = \min(\text{索引 }1, \text{索引 }2) = 1$
• $r = \max(\text{索引 }1, \text{索引 }2) = 2$
• 区间长度 = $2 - 1 + 1 = 2$
• $x = 2 \ge 2$ → "YES" ✓

示例 2

$n=6, x=3$，状态：$1,0,1,1,0,0$

• $l = \min(0,2,3) = 0$
• $r = \max(0,2,3) = 3$
• 区间长度 = $3 - 0 + 1 = 4$
• $x = 3 < 4$ → "NO" ✓

示例 3

$n=8, x=8$，状态：$1,1,1,0,0,1,1,1$

• $l = \min(0,1,2,5,6,7) = 0$
• $r = \max(0,1,2,5,6,7) = 7$
• 区间长度 = $7 - 0 + 1 = 8$
• $x = 8 \ge 8$ → "YES" ✓

示例 4

$n=1, x=2$，状态：$1$

• $l = 0, r = 0$
• 区间长度 = $0 - 0 + 1 = 1$
• $x = 2 \ge 1$ → "YES" ✓

示例 5

$n=5, x=1$，状态：$1,0,1,0,1$

• $l = \min(0,2,4) = 0$
• $r = \max(0,2,4) = 4$
• 区间长度 = $4 - 0 + 1 = 5$
• $x = 1 < 5$ → "NO" ✓