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   
输出：_________

阅读程序写结果：

答案

11

题解

考点定位

前缀和与分界位置枚举。

解题过程

a[i] 保存第 i 位的 0/1 值，b[i] 保存前 i 位中 1 的个数。逆序扫描到 i 时，t 保存区间 [i,n] 中 0 的个数。

因此 b[i−1]+t 表示把前缀 [1,i−1] 全改成 0、后缀 [i,n] 全改成 1 所需的修改次数。res 初始为 b[n]，还覆盖了全部改成 0 的情况。

本题字符串长度为 28。扫描所有分界点，最小值出现在前缀长度为 3 时：前缀 100 有 1 个 1，剩余后缀有 10 个 0，共需修改 1+10=11 位。

答案：11。

易错提醒

a 的下标是字符串位置，b 是前缀和；它们不是按 ASCII 编码索引的字符计数表。