题目内容

小红有一个长度为$N$且只由字符$0、1$组成的字符串$S$，下标从$1$开始。

她每次可以对一个字符执行翻转操作，即$0$变$1$或者把$1$变成$0$。

题解

给定一个仅包含 '0' 和 '1' 的字符串 S，我们需要计算所有子区间的权值之和。定义每个子区间的权值为将该子区间内的所有数字变为 '0' 或 '1' 所需要的最少翻转次数。对于一个子区间，记 '0' 的个数为 c0，'1' 的个数为 c1，则最少翻转次数为：

$\text{min}(c0, c1) =$$\frac{c0 + c1 - |c0 - c1|}{2}$

即：

$\frac{\text{区间长度} - |c0 - c1|}{2}$