A25137. 彩色气球
题目描述
彩色气球
题目描述：
将 n 个气球排成一行，其中每个气球的颜色用数字表示，1 表示红色，2 表示绿色，3 表示蓝色。我们需要移除一些气球，使得任意相邻的两个气球颜色都不同。请计算最少需要移除多少个气球。
例如：n = 8，8 个气球的颜色依次为 1，1，1，3，2，2，3，1。
最少需要移除 3 个气球，可以使得任意相邻的两个气球颜色都不同，其中一种方案：
移除第 2 个、第 3 个和第 6 个气球。
移除后气球颜色依次为 1，3，2，3，1。
输入描述：
第一行输入一个整数 n（1≤n≤5000），表示气球的数量；
第二行输入 n 个整数（1≤整数≤3），依次表示这一行气球的颜色，红色为 1，绿色为 2，蓝色为 3，整数
之间以一个空格隔开。
输出描述：
输出一个整数，表示最少需要移除的气球数量。
样例输入：
8
1 1 1 3 2 2 3 1 样例输出：
3参考答案
#include <iostream>
using namespace std;
int main() {
int n, last, count = 0;
cin >> n >> last;
for (int i = 1, color; i < n; i++) {
cin >> color;
if (color == last) count++;
else last = color;
}
cout << count << endl;
return 0;
}答案解析
我们可以使用贪心策略。遍历气球，如果当前气球与上一个气球颜色相同，则移除当前气球（计数加一），否则保留。注意，我们只关心连续相同的气球，因为相邻不同不需要移除。实际上，我们只需要统计连续相同的气球段，然后对于每一段连续相同的气球，需要移除的个数为连续段长度减1。但注意，题目要求的是任意相邻两个气球颜色不同，所以当我们遇到连续相同的时候，我们只保留连续段中的第一个，移除后续的相同颜色直到颜色改变。因此，遍历数组，如果当前元素和前一个元素相同，就移除当前元素（计数加一），否则继续。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int removeCount = 0;
// 从第二个气球开始（下标1），如果当前气球和前一个气球相同，则移除当前气球（计数）
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i-1]) {
removeCount++;
}
}
// 但是注意：可能存在连续的超过2个相同，比如三个连续相同，那么我们需要移除两个（第一个保留，后面两个都要移除吗？）
// 实际上，上述方法只能处理相邻两个相同，对于连续多个相同，比如[1,1,1]：
// 第一次比较：第二个1和第一个1相同 -> 移除第二个1（计数1），然后第三个1和第二个1比较（但第二个1已经被移除了，所以第三个1实际和第一个1比较？）
// 然而，我们移除气球后，下一个气球会紧接着上一个保留的气球。所以我们在遍历时，当发现一个气球和上一个保留的气球相同，就移除。
// 因此，我们不需要改变数组，只需要记录上一个保留的气球颜色。但是，如果我们移除了当前气球，那么下一个气球应该与上一个保留的气球比较，而不是被移除的。
// 重新设计：使用两个指针，一个指向当前保留的位置，另一个遍历
// 或者，我们可以这样：遍历数组，用一个变量记录上一个保留的气球颜色，初始化保留第一个气球，然后从第二个开始，如果当前气球和上一个保留的气球颜色相同，则移除（计数）；否则，更新保留的气球为当前气球。
int last = arr[0];
int count = 0;
for (int i = 1; i < n; i++) {
if (arr[i] == last) {
count++;
} else {
last = arr[i]; // 保留当前气球，更新last
}
}
// 这样即可
cout << count << endl;
delete[] arr;
return 0;
}注意：样例输入[1,1,1,3,2,2,3,1]：
第一个气球1保留，last=1。
第二个气球1与last相同，移除，计数=1。
第三个气球1与last（还是1）相同，移除，计数=2。
第四个气球3与last（1）不同，保留，更新last=3。
第五个气球2与last（3）不同，保留，更新last=2。
第六个气球2与last（2）相同，移除，计数=3。
第七个气球3与last（2）不同，保留，更新last=3。
第八个气球1与last（3）不同，保留。
这样计数为3，符合样例输出。