📝 题目大意

给定 $N$ 只史莱姆排成一列，每只有一种颜色 $a_i$。若相邻两只颜色相同则会合体。每次魔法可将任意一只史莱姆改为任意颜色（共 $10000$ 种可选）。求最少施展魔法次数，使得没有相邻史莱姆颜色相同。

💡 解题思路

1. 题目分析：题目本质是：给定一个序列，每次可以将任意位置改为任意值，求最少修改次数使得序列中不存在相邻相等元素。数据范围 $N \leq 100$，颜色种类 $10000$ 远大于 $N$，意味着我们永远有足够的"新颜色"可用，无需担心颜色不够。

2. 算法推导：

   • 朴素想法：对于每一段连续相同颜色的区间，长度为 $L$，我们需要将其"打散"。最优策略是每隔一个位置修改一次，即需要修改 $\lfloor L/2 \rfloor$ 次。
   • 贪心扫描：从左到右遍历，维护 last_color 表示上一个确定下来的颜色。当遇到 a[i] == last_color 时，说明出现了相邻相同，此时必须修改当前这只史莱姆。由于颜色种类足够多，我们可以把它改成一个既不等于左边也不等于右边的颜色，然后令 last_color = -1（哨兵值，表示这只史莱姆已被修改，其颜色与任何真实颜色都不同），这样在下一轮比较时 a[i+1] 不可能等于 -1，相当于自动"跳过"了被修改的史莱姆对后续的影响。
   • 正确性：对于连续相同颜色的段，该贪心策略等价于"修改第 2, 4, 6, ... 个"，恰好是 $\lfloor L/2 \rfloor$ 次，达到下界。且每次修改只影响当前局部，不会破坏已处理前缀的合法性，因此贪心选择具有最优子结构。

3. 边界与细节：

   • 当 $N=2$ 且两数相同时，答案为 $1$，算法正确。
   • 当序列已经满足条件（如样例 2 的 1 2 1），magic_count 始终为 $0$，算法正确。
   • 哨兵值 -1 必须在颜色取值范围 $[1, 10000]$ 之外，确保不会与真实颜色误匹配。
   • 无需担心溢出，$N \leq 100$，计数器最多为 $\lfloor N/2 \rfloor \leq 50$。

⏱️ 复杂度分析

• 时间复杂度：仅需一次从左到右的线性扫描，每个元素访问一次，$O(N)$。
• 空间复杂度：仅需存储长度为 $N$ 的数组 a 以及几个标量变量，$O(N)$。若采用在线读入（边读边处理），可优化至 $O(1)$ 额外空间，但 std.cpp 使用了 vector 存储全部输入，故为 $O(N)$。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int magic_count = 0;          // 记录施展魔法的次数
    int last_color = a[0];        // 上一个确定下来的颜色，初始为第一只史莱姆的颜色
    for (int i = 1; i < N; i++) {
        if (a[i] == last_color) { // 发现相邻相同颜色
            magic_count++;        // 必须修改当前这只史莱姆
            last_color = -1;      // 哨兵值，表示当前史莱姆已被修改，颜色与任何真实颜色都不同
        } else {
            last_color = a[i];    // 无需修改，更新 last_color 为当前颜色
        }
    }
    cout << magic_count << endl;    
    return 0;
}