题解（算法）

算法

读取字符串 s
n = s 的长度
计算 totalOnes （s 中 '1' 的数量）
totalZeros = n - totalOnes

prefOnes[0] = 0
for i = 0 … n-1
prefOnes[i+1] = prefOnes[i] + (s[i]=='1')

answer = min(totalZeros , totalOnes) // i = 0 （整个字符串变为一种类型）
for i = 1 … n // 尝试每一个可能的分割点
ones = prefOnes[i]
zeros = i - ones
cost1 = totalZeros + 2ones - i
cost2 = totalOnes + i - 2ones
answer = min(answer, min(cost1,cost2))

output answer

---

3. 正确性证明

我们证明该算法输出的是所需翻转次数的最小值。

---

引理 1

对于每个分割位置 i，值 cost1(i)（公式 (1)）等于将字符串转换为形式 0…0 1…1 且分割点位于位置 i 时所需翻转的位数。

证明。
前缀 s[0…i‑1] 必须全变为 0。所有初始为 1 的位置都必须被翻转；这样的位置共有 ones[i] 个。
后缀 s[i…n‑1] 必须全变为 1。其中初始为 0 的位置都必须被翻转；这样的位置共有 totalZeros - zeros[i] 个。
将这两个数量相加即得公式 (1)。 ∎

引理 2

对于每个分割位置 i，值 cost2(i)（公式 (2)）等于将字符串转换为 1…1 0…0 形式且分割点位于 i 时所需的最少翻转次数。

证明。 与引理 1相同，只是0和1的角色互换。∎

引理 3

对于固定的分割位置i，得到所有0和所有1各自连续的最便宜方式，其代价为min(cost1(i), cost2(i))。

证明。
所有0在所有1之前，或者所有1在所有0之前，这两种情况互斥穷尽。
根据引理 1，第一种情况的最小代价为cost1(i)；根据引理 2，第二种情况的最小代价为cost2(i)。这两者中较小者即为该分割下的最优解。∎

引理 4

算法计算出的 answer 等于

min_{0≤i≤n} min( cost1(i) , cost2(i) )

证明。
外层循环恰好遍历每个分割点 i = 1 … n。
循环内部计算 ones = prefOnes[i]，zeros = i‑ones，
然后利用公式 (1) 和 (2) 计算 cost1(i) 和 cost2(i)。
因此，min(cost1(i), cost2(i)) 会被检查，并与当前变量 answer 取最小值。
初始值 answer = min(totalZeros,totalOnes) 对应于分割点 i = 0 的情况。
因此，循环结束后，answer 存储了上述全局最小值。 ∎

引理 5

answer 等于将整个字符串转换为任意一个可接受最终形态所需的最少翻转次数。

证明。
每个可接受的最终形态恰好是某个分割点 i 对应的两种形态 0…0 1…1 或 1…1 0…0 之一。
根据引理 3，对于该分割点，最优的翻转次数为 min(cost1(i), cost2(i))。
因此，在所有分割点上的最优解就是对所有这些值取最小值，而这恰好就是 answer（引理 4）。 ∎

定理

程序输出的是使得所有 0 和所有 1 各自形成连续段所需的最少位翻转次数。

证明。
由引理 5 直接可得。∎

---

4. 复杂度分析

n – 输入长度 (≤ 10⁶)

• 时间 – 对字符串进行一次遍历，O(n)。
• 内存 – 大小为 n+1 的 int 类型前缀数组，即 O(n) 个整数（在最大数据下约 4 MiB）。
  如果显式存储前缀数组，则将内存使用减少到 O(1)。

---

5. 参考实现 (GNU-C++17)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size();

    long long totalOnes = 0;
    for (char c : s) if (c == '1') ++totalOnes;
    long long totalZeros = n - totalOnes;

    // 读取前缀中 1 的个数
    vector<int> prefOnes(n + 1, 0);          // prefOnes[i] = s[0..i-1] 中 1 的个数
    for (int i = 0; i < n; ++i) {
        prefOnes[i + 1] = prefOnes[i] + (s[i] == '1');
    }

    long long answer = min(totalZeros, totalOnes);   // i = 0 的情况（全部变为一种类型）

    for (int i = 1; i <= n; ++i) {
        long long ones  = prefOnes[i];
        long long zeros = i - ones;

        long long cost1 = totalZeros + 2 * ones - i;          // 0...0 1...1
        long long cost2 = totalOnes  + i - 2 * ones;          // 1...1 0...0

        answer = min(answer, min(cost1, cost2));
    }

    cout << answer << '\n';
    return 0;
}