Codeforces 266A：Stones on the Table

题目要做什么

桌面上有一串按颜色排列的石块。删除相邻且颜色相同的多余石块，求最少删除数。

这道题不需要模拟删除过程，只需从左到右检查相邻字符：

• 当前字符与前一个字符相同：当前石块必然需要删除，count++；
• 当前字符不同：保留当前石块；
• 扫描从 i = 1 开始，因为 s[0] 没有前一个字符。

从 C 思维切换到 C++

输入是一整个字符串，不是单个 char，因此直接使用 string：

string s;
cin >> s;

这题不需要 malloc、free、指针函数或额外的 vector。核心就是一次线性扫描：

int count = 0;
for (int i = 1; i < n; i++)
{
    if (s[i] == s[i - 1])
    {
        count++;
    }
}

第一位会自然参与第一次比较：s[1] 与 s[0] 比较，不需要单独统计 s[0]。

完整 C++ 实现

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int count = 0;
    for (int i = 1; i < n; i++)
    {
        if (s[i] == s[i - 1])
        {
            count++;
        }
    }

    cout << count << '\n';
    return 0;
}

n 是字符串长度，s.size() 也可以作为循环上界；使用 n 时要确保它与字符串长度一致。

示例

输入：
3
RRR

输出：
2

三个相同颜色的石块最多保留一个，因此需要删除两个。

复杂度

• 时间复杂度：O(n)，只扫描一次字符串；
• 空间复杂度：O(1)，除输入字符串外没有额外数据结构。

这次暴露出的典型误区

1. 不要把简单字符串题写成指针和动态内存流程

string 已经能完成存储、下标访问和输入。先选择能直接表达题意的数据结构，再考虑是否需要额外内存。

2. 循环必须从 i = 1 开始

从 i = 0 开始会访问 s[i - 1]，产生越界。第一个字符没有前驱。

3. 不必真的删除字符

每一对相邻相同字符贡献一次删除数，只计数即可得到答案。

4. 建立 C++ 标准库映射

一串字符      → string
动态数组      → vector
去重集合      → set
键值统计      → map
排序          → sort

这题只需要 string。

Windows 下编译运行

在保存 266A.cpp 的目录中执行：

g++ -std=c++17 266A.cpp -o 266A.exe
.\266A.exe

如果 g++ 无法识别，先检查：

g++ --version
where g++

必要时把 MSYS2/UCRT64 的 bin 目录加入系统 Path，然后重新打开终端。

一句话总结

读取 n 和字符串
→ 从第二个字符开始扫描
→ 比较相邻字符
→ 相同就 count++
→ 输出 count

这道 800 分题训练的重点不是复杂算法，而是从 C 的手动处理切换到 C++ 的 string 与直接、清晰的线性扫描。