📝 题目大意

有 $L$ 把椅子排成一列，$N$ 组人依次到来，每组 $1$ 或 $2$ 人，总人数恰好等于 $L$。每组随机选择一个能容纳本组人数的连续空位坐下。判断是否无论随机选择如何，都能保证所有组全部坐下而无人离开。

💡 解题思路

1. 题目分析：每组只有 $1$ 人或 $2$ 人（$a_i \in \{1,2\}$），且总人数之和等于 $L$。唯一会导致有人无法坐下的情况是：某组 $2$ 人到来时，剩余空位全部分散为孤立单椅（即不存在任何两个相邻空位）。因此问题转化为：是否存在一种最坏情况的随机选择，使得在某个 $2$ 人组到来时，所有剩余空位都是孤立的。

2. 算法推导： 考虑一个对抗者（adversary），他可以在每组到来时选择最不利的放置位置，试图最大化"孤立单椅"的数量。我们维护两个变量：

   • $L$：当前剩余椅子中，属于某个"连续大块"的椅子数（即非孤立的椅子总数）。
   • $one$：当前已经被孤立出来的单椅数量。

   初始时 $L$ 为总椅子数，$one = 0$，即所有椅子在一个大连续块中。

   对抗者的最优策略始终是：将当前组放在连续块的边界，尽可能制造孤立单椅。具体地：

   • 处理 $1$ 人组：

     • 若 $L = 0$：连续块已空，只能消耗一个孤立单椅（$one \leftarrow one - 1$）。
     • 若 $L = 1$：连续块恰剩 $1$ 椅，直接使用，块消失（$L \leftarrow 0$）。
     • 若 $L \geq 2$：对抗者将 $1$ 人放在连续块边界，占据 $1$ 椅，同时将相邻的 $1$ 椅割裂为孤立单椅。因此连续块缩小 $2$（$L \leftarrow L - 2$），孤立单椅增加 $1$（$one \leftarrow one + 1$）。

   • 处理 $2$ 人组：

     • 若 $L \leq 1$：连续块中无法容纳 $2$ 人，且孤立单椅也无法容纳 $2$ 人 → 输出 No。
     • 若 $L = 2$：连续块恰为 $2$ 椅，恰好容纳（$L \leftarrow 0$）。
     • 若 $L \geq 3$：对抗者将 $2$ 人放在连续块边界，占据 $2$ 椅，割裂相邻的 $1$ 椅为孤立单椅。连续块缩小 $3$（$L \leftarrow L - 3$），孤立单椅增加 $1$（$one \leftarrow one + 1$）。

   正确性说明：为什么对抗者每次只制造 $1$ 个孤立单椅？因为 $a_i \in \{1,2\}$，一组最多占据 $2$ 个连续位置，在边界放置时最多只能将 $1$ 个相邻椅子与主块割裂。对抗者无法通过一次放置制造更多孤立单椅。同时，制造孤立单椅总是有利于对抗者（孤立单椅只能容纳 $1$ 人组，对后续 $2$ 人组构成威胁），因此该策略确实是最优的。

   如果遍历完所有组后仍未触发 No，则说明即使最坏情况也无法迫使任何人离开，输出 Yes。

3. 边界与细节：

   • 当 $L = 0$ 且 $one > 0$ 时，只有 $1$ 人组能消耗孤立单椅，$2$ 人组会直接失败。
   • 变量 one 可能变为负数吗？不会，因为 $L + one$ 始终等于剩余椅子总数，且 $L \geq 0$，只有当 $L = 0$ 且 $one > 0$ 时才会 one--，此时 $one$ 至少为 $1$。
   • 数据范围 $N \leq 2 \times 10^5$，$O(N)$ 的模拟完全可行。

⏱️ 复杂度分析

• 时间复杂度：仅需对 $N$ 个组进行一次线性扫描，每次 $O(1)$ 处理，总复杂度 $O(N)$。
• 空间复杂度：仅使用常数个变量（L、one、a），无需额外数组，空间复杂度 $O(1)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, L; 
    cin >> N >> L;
    int one = 0;                // 已制造出的孤立单椅数量
    while(N--){
        int a; 
        cin >> a;
        if(a == 1){
            if(L == 0)
                one--;          // 连续块已空，消耗一个孤立单椅
            else if(L == 1)
                L--;            // 连续块仅剩1椅，直接使用
            else
                L -= 2, one++;  // 从连续块取2椅，用1椅，留1椅孤立
        } else {                // a == 2
            if(L <= 1){
                cout << "No\n"; // 无法容纳2人组，对抗者获胜
                return 0;
            }
            if(L == 2)
                L -= 2;         // 连续块恰为2椅，恰好容纳
            else
                L -= 3, one++;  // 从连续块取3椅，用2椅，留1椅孤立
        }
    }
    cout << "Yes\n";            // 所有组均能坐下
}