喵~ 主人好呀！今天由我，你最可爱的小猫娘，来为你讲解 Codeforces 上的这道 "False Alarm" 题目！这道题就像逗猫棒一样，看起来晃来晃去有点复杂，但只要找准了核心，一下子就能抓住啦！下面就跟我一起来看看吧，nya~

A. False Alarm - 一场虚惊喵~

题目大意

这道题是说，有一个叫 Yousef 的小哥，他要穿过一条有 n 扇门的走廊。这些门有些是开的（用 0 表示），有些是关的（用 1 表示）。

规则是这样的喵：

他必须按顺序从第 1 扇门走到第 n 扇门。
通过一扇开着的门需要 1 秒。
如果门是关着的，他就过不去，会被卡住。
不过呢，他有一个超厉害的按钮！这个按钮最多只能按一次。
一旦按下，所有关着的门都会立刻打开，并且这个效果会持续 x 秒。

那么问题来了：Yousef 小哥到底能不能成功穿过所有门，到达走廊的尽头呢？

解题思路

要怎么才能最有效地使用那个神奇按钮呢？喵？

这个按钮的效果只能持续 x 秒，而且只能用一次。为了让这宝贵的 x 秒发挥最大作用，我们肯定不希望浪费它。

主人请想一下，我们什么时候最需要这个按钮呢？当然是遇到第一扇被关上的门的时候啦！

如果我们在遇到第一扇关着的门之前就按按钮，那在走到那扇门之前，按钮的效果时间就已经在流逝了，太浪费了，喵！
如果我们想留着按钮，等遇到后面的关着的门再按，那我们连第一扇关着的门都过不去呀！

所以，最聪明的做法（也就是贪心策略）就是：当我们走到第一扇关着的门前时，立刻按下按钮！ 这样可以确保按钮的 x 秒效果，能覆盖到尽可能多的、从这扇门开始的后续路程。

好，策略定下来了！那我们来分析一下时间。假设我们从走廊入口（第 1 扇门前）出发的时刻是 0。因为通过每扇门都需要 1 秒，所以我们到达第 i 扇门前的时间点就是 i-1 秒。

我们先在门的状态数组里，找到第一扇关着的门的位置，记作 first_closed。
再找到最后一扇关着的门的位置，记作 last_closed。

根据我们的贪心策略，我们会在到达 first_closed 门前的时刻，也就是 first_closed - 1 秒时，按下按钮。

按下按钮后，开门效果会从 first_closed - 1 秒开始，持续 x 秒。也就是说，在时间点 t，只要满足 first_closed - 1 <= t < (first_closed - 1) + x，我们遇到的任何关着的门都是可以通行的。

现在，我们最关心的是，当我们走到最后一扇关着的门 last_closed 时，按钮的效果还在不在。我们到达 last_closed 门前的时间点是 last_closed - 1 秒。

为了能通过这最后一扇门，必须满足： last_closed - 1 < (first_closed - 1) + x

我们来简化一下这个不等式，两边都加上 1： last_closed < first_closed + x

看，结论就出来啦！只要最后一扇关门的编号，小于第一扇关门的编号加上按钮的持续时间 x，Yousef 就能成功通过。否则就不行。

是不是很简单，就像追着自己的尾巴转圈圈一样，一下子就想明白了，喵~

举个例子：n=4, x=2, 门是 0 1 1 0

第一扇关着的门是第 2 扇，first_closed = 2。
最后一扇关着的门是第 3 扇，last_closed = 3。
我们来判断 last_closed < first_closed + x 是否成立。
3 < 2 + 2，也就是 3 < 4。这是成立的！
所以答案是 "YES"。

再举个例子：n=6, x=3, 门是 1 0 1 1 0 0

first_closed = 1。
last_closed = 4。
判断 4 < 1 + 3，也就是 4 < 4。这不成立！
所以答案是 "NO"。

代码实现

下面是解题的代码，和我刚才的思路一模一样哦！这段代码就像猫猫我一样，虽然看起来简单，但爪子可是很锋利的哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n, x;
    std::cin >> n >> x;
    
    // 用-1来表示我们还没找到关着的门
    int first_closed = -1;
    int last_closed = -1;
    
    // 遍历所有的门，找到第一扇和最后一扇关着的门
    for (int i = 0; i < n; ++i) {
        int door_state;
        std::cin >> door_state;
        if (door_state == 1) { // 发现一扇关着的门！
            if (first_closed == -1) {
                // 如果是第一次发现，就记下它的位置（用1-based index）
                first_closed = i + 1;
            }
            // 每次发现关着的门，都更新最后一扇门的位置
            last_closed = i + 1;
        }
    }
    
    // 套用我们推导出的神奇公式！
    if (last_closed < first_closed + x) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

知识点时间~

贪心算法 (Greedy Algorithm)

这道题的核心就是贪心算法。贪心算法就是每一步都做出当前看起来最好的选择，而不从整体最优上进行考虑。就像猫猫看到晃动的毛线球就忍不住扑上去一样，我们在这里选择在“最需要”的时刻——也就是遇到第一扇关门时——使用唯一的道具。幸运的是，在这个问题里，这个局部最优选择恰好就是全局最优解！

问题简化

这个问题初看似乎和时间、移动、状态变化有关，有点让人头晕。但通过分析，我们发现决定结果的关键因素只有三个：第一扇关门的位置、最后一扇关门的位置、以及按钮的持续时间 x。我们成功地把一个动态过程简化成了一个静态的数值比较，这就是解题中非常重要的“化繁为简”思想，喵~

好啦，这次的题解就到这里啦！希望这篇讲解能帮到主人哦！如果还有什么问题，随时可以再来找我！下次再见，喵~ (ฅ'ω'ฅ)

A. False Alarm - 一场虚惊喵~ ​

题目大意 ​

解题思路 ​

代码实现 ​

知识点时间~ ​

贪心算法 (Greedy Algorithm) ​

问题简化 ​