1.题目分析
题目要求我们对一个二进制字符串进行操作，具体来说，就是将其中的0全部移除，每一次操作可以选择翻转两个不相邻的位置，使得翻转后的操作字符中可以正确的移除0。题目要求输出最小的非相邻对翻转次数，使得操作后字符串中的“0”全部被移除。解决这个问题，可以使用贪心算法，从字符串的开头到结尾逐步考虑每一个字符，每一步尽可能的减少操作步骤，最终得到最小的非相邻对翻转次数。
2.解题思路
2.1 贪心策略
对于这种最优解问题，可以采取贪心策略，设答案为 $ans$，每次贪心地选择一个位置 $i$，令当前剩下的未去除 0 的个数为 $sum_0$，令当前考虑的位置为 $j \in [i + 1, n]$，令 $len_{j - i - 1}$ 表示区间 $[i + 1, j - 1]$ 中非 $0$ 的元素个数，策略如下：
若 $a_i = 0$ 且 $len_{j - i - 1} \geq 1$，那么当前位置可以选择留下不操作，因为它后面一定有其它的非 $0$ 元素；
若 $a_i = 0$ 且 $len_{j - i - 1} = 0$，只能选择一个非 $i + 1$ 的位置进行翻转，否则就无法去除所有的 $0$；
若 $a_i = 1$，那么当前的位置也可以选择留下不操作，因为它后面一定会有 $0$。
2.2 代码实现
实现时需要记录最近一次翻转的位置 $last\_flip$，逐个字符扫描并执行上述策略。时间复杂度 $O(n)$。贪心策略可保证最后的答案就是最优解，也即不存在后效性问题。
#include<bits/stdc++.h>
using namespace std;
int n, len, ans = 0;
string str;
int main() {
cin >> str;
n = str.length();
for(int i = 0; i < n; i++) {
if(str[i] == '0') {
if(len >= 1) {
len--;
} else {
// 找到一个不连续的1进行翻转
for(int j = i + 1; j < n; j++) {
if(str[j] == '1' and j != last_flip) {
swap(str[i], str[j]);
ans++;
last_flip = j;
break;
}
}
len = 0;
if(str[i] == '0') {
ans++;
last_flip = i;
}
}
} else {
len++;
}
}
cout << ans;
return 0;
}
3.代码小结
代码部分主要就是对贪心策略的实现，主要分三种情况讨论，细节方面处理好每次操作后的更新即可。
4.总结
该题目可以锻炼我们单纯的贪心算法的思想，并使我们进一步地深入理解贪心的方法。同时也涉及到了字符串的操作，考验了我们理论与实践实力的综合水平。总体来说，该题目既有一定难度又不失是一道入门级别的算法题。