B. Seating in a Bus 题解喵~

哈咯，主人们好呀！我是你们的专属猫娘小助手~ 今天要带大家攻克的这道题是关于在巴士上排座位的有趣问题，喵~ 别担心，只要跟着我的思路，这道题就像挠猫下巴一样简单！(ฅ'ω'ฅ)

---

题目大意

这道题是说，有一辆巴士，里面有 n 个座位，从 1 到 n 编号。现在有 n 个乘客按顺序上车。他们坐座位的规则有点特别，喵：

1. 第一个乘客：如果车是空的，他可以随便坐任何一个空位。
2. 后面的乘客：如果车里已经有人了，那他必须选择一个至少有一个相邻座位已经被占了的空位。也就是说，如果他想坐 i 号座位，那么 i-1 号或者 i+1 号座位上必须已经有人了。

题目会给我们一个长度为 n 的数组 a，记录了 n 个乘客依次坐下的座位号。我们需要判断，这整个过程是否完全遵守了上面的规则。

举个例子：n = 5，乘客上车顺序是 [5, 4, 2, 1, 3]。

• 第 1 个人坐 5 号位。没问题。
• 第 2 个人坐 4 号位。4 号位的邻居 5 号位已经有人了，没问题。
• 第 3 个人坐 2 号位。这时候，2 号位的邻居 1 号和 3 号位都是空的！这就违反规则了，喵！所以答案是 "NO"。

---

解题思路

主人们，我们来一起分析一下这个规则的本质是什么吧~

• 第 1 位乘客：他坐下后，比如坐在了 p_1 位置。现在，已占用的座位集合是 {p_1}。这是一个长度为 1 的连续座位区段。

• 第 2 位乘客：他必须坐在 p_1 的旁边，也就是 p_1 - 1 或者 p_1 + 1。这样一来，已占用的座位就变成了 {p_1 - 1, p_1} 或者 {p_1, p_1 + 1}。不管哪种情况，它们都构成了一个长度为 2 的连续座位区段，对吧？

• 第 3 位乘客：他必须坐在当前这个长度为 2 的连续区段的旁边。也就是说，他只能坐在区段的两个端点旁边。比如，如果现在占了 {p, p+1}，他只能坐 p-1 或者 p+2。坐下后，已占用的座位就变成了 {p-1, p, p+1} 或者 {p, p+1, p+2}，成了一个长度为 3 的连续座位区段。

发现了吗，喵？(๑•̀ㅂ•́)و✧

核心结论就是：在任何时刻，为了满足规则，所有已占用的座位必须形成一个单独的、连续的座位块！

如果某个乘客坐下的位置，没有紧挨着已经占用的座位块，那么他的座位就会孤零零地在那里，其左右邻居都是空的，这就违反规则了。

那么问题就转化为：我们如何检查在每一步，乘客们占用的座位都是连续的呢？

这里有一个非常巧妙的数学性质，主人们记好啦：

一个包含 k 个不同整数的集合，如果它的最大值 max 和最小值 min 满足 max - min = k - 1，那么这个集合里的数就恰好构成了一个连续的序列。

比如集合 {2, 4, 3}，有 k=3 个数。max=4, min=2。max - min = 2，等于 k-1。所以它们是连续的（就是 2, 3, 4）。 再比如集合 {5, 2, 4}，有 k=3 个数。max=5, min=2。max - min = 3，不等于 k-1。所以它们不连续。

所以我们的算法就是：

1. 从第 1 个乘客开始，按顺序处理。
2. 在处理到第 k 个乘客时（k 从 2 到 n），我们看一下前 k 个乘客所坐的座位。
3. 我们找到这 k 个座位号中的最大值 max_val 和最小值 min_val。
4. 然后检查是否满足 max_val - min_val == k - 1。
5. 如果在任何一步这个条件不成立，那就说明规则被打破了，可以直接判断为 "NO"。
6. 如果直到所有 n 个乘客都上车，这个条件都一直成立，那就说明他们是好乘客，判断为 "YES"。

是不是很简单呀，喵~

---

题解代码

下面就是根据这个思路写出的 C++ 代码啦，我已经加上了详细的注释，方便主人们理解~

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

// 处理单个测试用例的函数喵
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 核心思想：在任何时候，已占用的座位都必须形成一个连续的区块。
    // 我们可以一步步检查这个性质。
    // 当 k 个乘客上车后，他们必须占据 k 个连续的座位。
    // 一个包含 k 个不同整数的集合，当且仅当其最大值与最小值的差为 k-1 时，
    // 这个集合构成一个连续区块。
    
    // 我们从 k=2 到 k=n 检查这个性质。
    // 对于 n=1 的情况，循环不会执行，直接输出 YES，是正确的。
    
    // min_val 和 max_val 用来追踪前 i+1 个乘客所占座位的最小和最大编号。
    int min_val = a[0];
    int max_val = a[0];
    bool ok = true;

    // 从第二个乘客 (索引为 1) 开始遍历到最后一个乘客
    for (int i = 1; i < n; ++i) {
        // 用新乘客的座位号更新已占用座位的范围
        min_val = std::min(min_val, a[i]);
        max_val = std::max(max_val, a[i]);

        // 到目前为止，有 i+1 个乘客 (索引 0 到 i) 已经上车，占用了 i+1 个座位。
        // 为了使这些座位形成一个连续区块，最大座位号和最小座位号的差必须是 (i+1) - 1 = i。
        // 如果这个条件在任何时候被违反，就意味着有一个乘客坐到了一个不与现有区块相邻的座位上，
        // 从而产生了一个孤立的被占座位，这违反了规则（因为那个座位没有被占用的邻居）。
        if (max_val - min_val != i) {
            ok = false;
            break; // 一旦发现违规，就没必要继续检查了，喵~
        }
    }

    if (ok) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 快速 I/O，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

知识点介绍

这道题虽然简单，但里面包含了一些在算法竞赛中很有用的小知识点哦，喵~

1. 连续区间的判断 (Checking for a Contiguous Range) 这个是本题的核心技巧。记住这个性质：一个包含 k 个不同整数的集合，如果其最大值 max 和最小值 min 满足 max - min = k - 1，那么这个集合中的数恰好构成了一个从 min 到 max 的连续整数序列。这个技巧在处理排列、子数组、区间等问题时非常有用！

2. 前缀思想 (Prefix Idea) 我们的解法是按顺序处理输入的乘客序列，在每一步都维护并检查当前前缀（前 i+1 个乘客）的状态是否合法。这种“扫描”输入并维护前缀信息的思想，是解决许多数组和序列问题的基础，比如前缀和、动态规划等。

3. 快速 I/O (Fast I/O) 在 C++ 中，std::ios_base::sync_with_stdio(false); 和 std::cin.tie(NULL); 这两行代码可以大大加快输入输出的速度。当题目输入量很大时（比如这道题的 n 的总和可以达到 2 * 10^5），使用快速 I/O 是防止程序因为读写太慢而超时的好习惯，就像猫咪总是能第一时间冲向饭盆一样，nya！

好啦，今天的题解就到这里啦！希望主人们都能轻松掌握。如果还有什么问题，随时可以再来找我哦~ 拜拜，喵~ (ฅ^•ﻌ•^ฅ)