• 题目描述

小芳得到一个长度为 n 的字符串 s，仅由字符 0 和 1 组成。她可以进行任意次如下操作：

选择 s 的一个非空子序列，要求该子序列中任意两个相邻元素都不相同。 将该子序列中的 0 全部变为 1，1 全部变为 0（即 01 反置）。

小芳想知道，最少需要多少次操作，才能使字符串 s 满足任意两个相邻元素都不相同（即不存在相邻字符相同的情况）。

  • 名词解释

子序列：从原序列中删除任意个（可以为零或全部）元素后，保持剩余元素相对顺序不变得到的新序列。

01 反置：将字符串中的 0 全部变为 1，1 全部变为 0。

  • 题解思路：

通俗地说：想象你有一串由0和1组成的珠子，你的目标是把它们重新排列，让相邻的两个珠子颜色都不同（要么是010101...，要么是101010...）。 可以这样操作：

  • 从中挑出一些珠子（可以不连续），但这些被挑出的珠子本身必须是交替颜色的

  • 把这些挑出的珠子颜色翻转（0变1，1变0）

第一步：明确最终目标

最终结果只有两种可能：

模式A：010101...（从0开始）

模式B：101010...（从1开始）

我们不知道哪种更好，所以两种都要试试。

第二步：理解操作的本质

一次操作可以选择多个位置，但这些位置在原字符串中必须构成交替序列（如0,1,0,1...或1,0,1,0...）。

关键思想：我们可以把需要修改的位置分组，每一组可以在一次操作中完成。

第三步：贪心分组策略

假设我们要变成模式A（010101...）：从头开始扫描字符串，记录当前有哪些操作区间，以及它们以什么字符结尾，当遇到一个需要修改的位置时：

如果这个位置字符是'0'，看看有没有以'1'结尾的操作区间，如果有，就合并进去；如果没有，就新建一个以'0'结尾的操作区间，如果这个位置字符是'1'，看看有没有以'0'结尾的操作区间，如果有，就合并进去；如果没有，就新建一个以'1'结尾的操作区间

算法步骤

对于两种目标模式（010101...和101010...）分别计算

对每种模式： 初始化两个计数器：cnt0（以'0'结尾的操作区间数），cnt1（以'1'结尾的操作区间数）

遍历字符串的每个位置：计算当前位置在目标模式中应该是什么字符

如果实际字符与目标字符不同（需要修改）：如果是'0'：尝试与cnt1合并，然后增加cnt0，如果是'1'：尝试与cnt0合并，然后增加cnt1，这种模式需要的操作次数 = cnt0 + cnt1，取两种模式中较小的操作次数作为答案即可

ac码如下：（题解写的比较详细，ac码就不附注释了）

……省略头文件
//头文件有#define int long long 为了减少代码量没复制头文件
void solve() {
	int n;
	string s;
	cin >> n >> s;
	int ans = LLONG_MAX;
	for (int i = 0; i < 2; i++) {
		int cnt0 = 0, cnt1 = 0;
		for (int j = 0; j < n; j++) {
			char c = '0' + ((i + j) % 2);
			if (s[j] != c) {
				if (s[j] == '0') {
					if (cnt1 > 0)
						cnt1--;
					cnt0++;
				} else {
					if (cnt0 > 0)
						cnt0--;
					cnt1++;
				}
			}
		}
		int cz = cnt0 + cnt1;
		ans = min(ans, cz);
	}
	cout << ans << endl;
}

signed main() {
	//vector<vector<int>>a(n,vector<int>(m)); 二维构造
	//cout << fixed << setprecision(10);  固定小数输出
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	cin >> T;
	while (T--) solve();
	return 0;
}

如发现错误，感谢指出和纠正