Moe's CF Life

喵~ 主人好呀！今天我们来看一道超级可爱的题目，就像在桌子上玩彩色的小石头一样！一起来看看怎么解决它吧！

A. Stones on the Table (桌上的石头)

题目大意

简单来说，就是桌子上有一排 n 个彩色的石头，颜色有红（R）、绿（G）、蓝（B）三种，喵~。

我们的任务是，拿走最少数量的石头，使得剩下的石头中，任何两个相邻的石头颜色都不相同。

比如说，RRG，中间两个 R 是相邻且同色的，我们得拿走一个 R，就变成了 RG，这样就满足条件啦。总共拿走了 1 个。

再比如 RRRRR，为了让相邻石头颜色不同，我们得拿走 4 个，只留下 1 个 R。

是不是很简单呀？喵~

题解方法

这个问题呀，其实用一个非常直观的方法就能解决，我们叫它“贪心”，就像小猫看到小鱼干就想立刻吃掉一样！(ฅ'ω'ฅ)

我们的策略是：

从左到右一个一个地检查石头。
我们从第二块石头开始，把它和它左边紧挨着的那块石头比较。
如果发现这两块石头的颜色是一样的（比如 RR 或者 BB），哎呀，它们太“亲密”了，必须拿走一个才能让它们分开！
所以，每当我们发现一对颜色相同的相邻石头，我们就把需要拿走的石头数量加一。

我们只需要把整排石头都这样检查一遍，最后得到的总数，就是最少需要拿走的石头数量啦。

为什么这样做是对的呢？因为我们拿走一块石头，最多只能解决一对相邻的冲突。比如 RRR，我们拿走中间的 R，就解决了两对冲突。但在这个题目里，我们只关心计数，拿走 s[i] 还是 s[i-1] 对后续的比较没有影响，因为我们总是拿当前石头和它左边的石头比。所以，每次遇到 s[i] == s[i-1] 就计数一次，正好对应了一次“拿走”操作，不多也不少，喵~

题解

下面是具体的 C++ 代码实现，让我来为主人一步步解释吧~

cpp

#include <iostream>
#include <string>
#include <vector>

int main() {
    // 这两行是为了让输入输出快一点点，虽然这题数据量很小，
    // 但养成好习惯总没错的，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 先读入石头的总数 n
    int n;
    std::cin >> n;

    // 再读入代表石头颜色的字符串 s
    std::string s;
    std::cin >> s;

    // 这个变量用来记录我们要拿走的石头数量
    int removals = 0;

    // 我们从第二块石头（下标为1）开始遍历
    // 每次都和它前面的那块（下标 i-1）比较
    for (int i = 1; i < n; ++i) {
        // 如果当前石头 s[i] 和它前一个 s[i-1] 颜色相同...
        if (s[i] == s[i - 1]) {
            // ...那我们就必须拿走一个！计数器+1
            // 这个贪心策略是正确的，因为每次移除只解决这一对相邻的冲突
            removals++;
        }
    }

    // 最后，把需要拿走的石头总数打印出来就好啦
    std::cout << removals << std::endl;

    return 0;
}

看吧，代码的思路就和我们刚刚想的一模一样，就是遍历一遍，遇到相同的邻居就记个数，超直观的，对吧？喵~

知识点介绍

这道题虽然简单，但也能学到一些小知识哦~

贪心算法 (Greedy Algorithm)
- 就像我们刚才做的那样，贪心算法就是在每一步选择中都采取在当前状态下最好或最优的选择，从而希望能导致结果是全局最好或最优的。对于这个问题，局部最优（发现一对相同颜色的相邻石头就移除一个）恰好等于全局最优（移除石头总数最少）。但要注意哦，贪心算法不是对所有问题都有效的，有时候只看眼前会吃大亏的喵！
字符串遍历
- 在 C++ 中，std::string 可以像数组一样通过下标来访问每一个字符。我们用一个 for 循环，从 i = 1 开始（因为我们要和前一个比较，所以从第二个元素开始），一直到字符串的末尾。这样 s[i] 和 s[i-1] 就正好是一对相邻的石头啦。
基础输入输出
- std::cin 用于从标准输入（通常是键盘）读取数据。
- std::cout 用于向标准输出（通常是屏幕）打印数据。
- std::endl 是一个操纵符，用于输出一个换行符并刷新输出缓冲区，确保我们能立刻看到结果，喵~

好啦，今天的解说就到这里啦！主人有没有觉得算法也很有趣呢？下次再一起学习吧，喵~ (´｡• ᵕ •｡`) ♡

A. Stones on the Table (桌上的石头) ​

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

A. Stones on the Table (桌上的石头)

题目大意

题解方法

题解

知识点介绍