思路

观察

​ 我们发现每次翻转只会使得01串1的个数变化偶数个。所以如果0的个数是奇数，那么0最后必定剩下1个。如果是偶数个，那么0可以全部变为1.

做法

​ 对于偶数个0.我们发现从第一个0开始，不断让相邻的0合并是最优解。

​ 对于奇数个0，我们发现需要空出1个0不操作。那么我们可以通过这个0将整个字符串分为str1+'0'+str2.其中str1和str2的0的数量都要保证是偶数个。这些要求满足后，我们可以求出str1和str2的操作次数，然后01串的操作次数就是这两个操作次数的和。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int zeroPos[200005];
int lastSum[200005];
int cnt = 0;
int main(){
    string str;
    cin >> str;
    for(int i = 0; i < str.length(); i++){
        if(str[i] == '0')zeroPos[++cnt] = i;//找到0的位置
    }
    if(cnt % 2 == 0){//如果是偶数
        int sum = 0;
        for(int i = 1; i <= cnt; i+=2){//直接合并相邻的
            sum += zeroPos[i + 1] - zeroPos[i];
        }
        cout << sum << endl;
    }else{
        lastSum[cnt + 1] = 0;
        for(int i = cnt - 1; i >= 1; i-=2){//后缀和来维护str2的操作次数
            lastSum[i] = lastSum[i + 2] + zeroPos[i + 1] - zeroPos[i];
        }
        int sum = (int)1e9;//答案，初始化最大值
        int pre = 0;//前缀和
        for(int i = 1; i <= cnt; i+=2){
            sum = min(sum, pre + lastSum[i + 1]);//求出最小的str1+str2
            pre += zeroPos[i + 1] - zeroPos[i];
        }
        cout << sum << endl;//输出
    }
}

python

s = input()
n = len(s)
cnt = 0
zeroPos = [0] * (n + 5)
lastSum = [0] * (n + 5)
for i in range (n):
	if s[i] == '0':
		cnt += 1
		zeroPos[cnt] = i
if cnt % 2 == 0:
	s = 0
	for i in range (1 , cnt + 1 , 2):
		s += zeroPos[i + 1] - zeroPos[i]
	print (s)
else:
	lastSum[cnt + 1] = 0
	for i in range (cnt - 1 , 0 , -2):
		lastSum[i] = lastSum[i + 2] + zeroPos[i + 1] - zeroPos[i]
	s = 1000000000
	p = 0
	for i in range (1 ,cnt + 1 , 2):
		s = min(s , p + lastSum[i + 1])
		p += zeroPos[i + 1] - zeroPos[i]
	print (s)

题目内容

曾经有一个小镇，镇上的居民都信奉一位神秘的数学家。这位数学家声名远扬，因为他曾经提出了一个关于二进制串的问题，而这个问题一直困扰着小镇上的居民。问题如下：

有一串由0和1组成的字符串，现在可以进行若干次如下操作：选择两个相邻的字符，将它们同时取反。例如，可以将00变成11，也可以将10变成01。请你求出最大化1字符数量的最小操作次数。

输入描述

一个长度不超过$200000$的、仅由’1'和’0组成的字符串。

输出描述

一个整数，代表最小的操作次数。

样例$1$

输入

010

输出

2

样例$2$

输入

111

输出

0

说明 无论怎么操作，1的数量最大值也只能是3，因此无需操作。