#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m=0;
    string s;
    cin>>n>>s;
    for(int i=0;i+2<=n-1;i++){
        if(s[i]=='#' && s[i+1]=='.' && s[i+2]=='#'){
            m++;
        }
    }
    cout<<m;
    return 0;
}

📝 题目大意

给定一个长度为 $N$ 的字符串 $S$，由 #（有人）和 .（无人）组成。统计满足 "座位 $i$ 和 $i+2$ 有人，座位 $i+1$ 无人" 的整数 $i$（$1 \le i \le N-2$）的个数。

💡 解题思路

1. 题目分析：$N \le 2 \times 10^5$，$S$ 仅由 # 和 . 构成。需要统计所有长度为 3 的连续子串中形如 #.# 的个数。数据范围要求 $O(N)$ 算法，直接扫描即可。

2. 算法推导：

   • 遍历 $i$ 从 $0$ 到 $N-3$（对应原题中的座位编号 $1$ 到 $N-2$）。
   • 对于每个位置 $i$，检查 s[i] == '#' && s[i + 1] == '.' && s[i + 2] == '#' 是否成立。
   • 若成立，ans++。
   • 最终输出 ans。

3. 边界与细节：

   • 当 $N < 3$ 时，循环条件 i < n - 2 不成立，直接输出 $0$，符合题意（样例 2 中 $N=1$ 输出 $0$）。
   • 注意字符串下标从 $0$ 开始，题目中座位编号从 $1$ 开始，对应关系为 s[i] 对应座位 $i+1$。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，仅需一次线性扫描。
• 空间复杂度：$O(N)$，用于存储字符串 $S$。

💻 标准代码 (C++)

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

int n, ans;      // n: 字符串长度, ans: 满足条件的个数
string s;        // 座位状态字符串

int main () {
    cin >> n >> s;
    // 遍历所有可能的 i（对应座位编号 1 到 N-2）
    for (int i = 0; i < n - 2; i++) 
        // 检查是否满足 #.# 模式
        if (s[i] == '#' && s[i + 1] == '.' && s[i + 2] == '#') ans++;
    printf("%d", ans);
    return 0;
}