题目详解：B. 公交车上的座位安排

问题理解

我们有 $n$ 个座位排成一行，编号 $1$ 到 $n$。
乘客按顺序上车，每个乘客必须遵守：

• 第 1 个乘客：可以任意坐（因为车上还没有人）。
• 第 2 个及以后的乘客：必须坐在某个至少有一个相邻座位已被占用的空座位上。

换句话说，当第 $i$（$i \ge 2$）个乘客坐下时，他的座位 $a_i$ 必须满足：
座位 $a_i - 1$ 或 $a_i + 1$ 中至少有一个已经被人坐了（即在前面的乘客中已经出现过）。

我们已知所有乘客按时间顺序坐下的座位编号数组 $a$，需要判断是否所有人都遵守了规则。

关键观察

如果我们把已经坐下的座位看作一个连续的区间吗？不一定，但我们可以注意到一个重要性质：

在任何时刻，所有已经被占用的座位一定构成一个连续的区间（没有间隔）。

为什么？

• 第 1 个人坐了一个座位，区间就是 $[a_1, a_1]$，是连续的。
• 第 2 个人必须坐在 $a_1 - 1$ 或 $a_1 + 1$，这会把区间向左或向右扩展 1 个位置，区间仍然连续。
• 第 3 个人必须坐在当前区间的左端点 $-1$ 或右端点 $+1$，否则就会产生空座位被跳过的情况。
• 依此类推，任何时候，所有已占座位一定是一个连续的区间 $[L, R]$。

算法思路

我们可以模拟这个过程：

1. 第一个乘客坐在 $a_1$，当前已占座位的区间为 $[L, R] = [a_1, a_1]$。
2. 对于第 $i = 2$ 到 $n$ 个乘客：
   • 如果 $a_i = L - 1$，说明他坐在当前区间左侧，更新 $L = a_i$。
   • 否则如果 $a_i = R + 1$，说明他坐在当前区间右侧，更新 $R = a_i$。
   • 否则，$a_i$ 既不是 $L - 1$ 也不是 $R + 1$，说明他坐在了一个非相邻的位置，违反了规则，输出 "NO"。
3. 如果所有乘客都满足条件，输出 "YES"。

示例分析

示例 1：$n = 5, a = [5, 4, 2, 1, 3]$

• 第 1 人坐 $5$，区间 $[5, 5]$。
• 第 2 人坐 $4$，$4 = 5 - 1$，合法，区间变为 $[4, 5]$。
• 第 3 人坐 $2$，$2$ 不是 $4-1=3$，也不是 $5+1=6$，不合法，输出 "NO"。

示例 2：$n = 3, a = [2, 3, 1]$

• 第 1 人坐 $2$，区间 $[2, 2]$。
• 第 2 人坐 $3$，$3 = 2 + 1$，合法，区间 $[2, 3]$。
• 第 3 人坐 $1$，$1 = 2 - 1$，合法，区间 $[1, 3]$。
• 输出 "YES"。

时间复杂度

• 每个测试用例只遍历一次数组，时间复杂度 $O(n)$。
• 所有测试用例的 $n$ 总和 $\le 2 \cdot 10^5$，总复杂度 $O(\sum n)$，足够快。

正确性证明

• 必要性：如果某人坐在非当前区间端点的相邻位置，那么他左右邻居要么是空（如果他在区间内部且不是端点），要么有一个邻居是空且另一个邻居是更早的座位，但根据规则，他必须至少有一个已占邻居。实际上，我们的判断 $a_i = L-1$ 或 $a_i = R+1$ 正是“至少有一个邻居被占”的唯一可能，因为当前已占座位是一个连续区间，只有两端外侧的座位才恰好有一个邻居被占，中间的座位虽然有两个邻居被占，但那些座位已经被占了，不可能再坐。
• 充分性：如果每次新乘客都坐在当前区间的左端 $-1$ 或右端 $+1$，那么他显然有一个邻居（原来的端点）已被占，符合规则，且新区间仍连续。

标程代码解读

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i : a) cin >> i;
    
    int left = a[0], right = a[0];  // 当前已占座位的区间
    
    for (int i = 1; i < n; i++) {
        if (a[i] + 1 == left)        // 坐在当前区间左侧
            left = a[i];
        else if (a[i] - 1 == right)  // 坐在当前区间右侧
            right = a[i];
        else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

这个解法非常简洁，利用了“已占座位始终连续”这一关键性质，只需要维护左右边界即可，不需要额外的布尔数组。