NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 25 题

阅读程序写结果：

#include<iostream>
using namespace std;
int main()
{
    string ch;
    int a[200];
    int b[200];
    int n, i, t, res;
    cin >> ch;
    n = ch.length();
    for (i = 0; i < 200; i++)
        b[i] = 0;
    for (i = 1; i <= n; i++)
    {
        a[i] = ch[i - 1] - '0';
        b[i] = b[i - 1] + a[i];
    }
    res = b[n];
    t = 0;
    for (i = n; i > 0; i--)
    {
        if (a[i] == 0)
            t++;
        if (b[i - 1] + t < res)
            res = b[i - 1] + t;
    }
    cout << res << endl;
    return 0;
}

输入：1001101011001101101011110001 输出：_________

看到前缀和数组 b 与倒序循环 → 先想枚举分界点求最小翻转次数

易错：a[i]存的是数字而非字符，b[i]是前缀和（1的个数），0的个数需通过下标减去 b[i] 计算

考点：程序阅读｜前缀和

程序在做什么

输入 01 串，求最少翻转几次使前面全 1 后面全 0。