【代码源】每日一题 非递减01序列

题目链接：非递减的01序列 - 题目 - Daimayuan Online Judge

题面

huaji有一个 01 序列，每次可以对其中的某一位取反（0变1，1变0）

求最少翻转其中的几位可以使得该序列变为非递减序列

输入格式

第一行输入一个整数 n (1≤n≤10^6)

第二行输入一个长度为 n 的且仅包含 0 和 1 的字符串

输出格式

输出一个整数，为该序列变为非递减序列的最少操作次数

输入样例

6
010110

输出样例

2

分析： 

非递减序列，不就是递增嘛，考虑最后的子串都是00……11……这种形式，就是由连续的0和连续的1构成，那么我们考虑枚举0和1的分界点，操作次数为分界点前面1的个数（1得变为0）加上分界点后面0的个数（0得变成1）。

详见代码：

#include <bits/stdc++.h>
using namespace std;
int ans = 1e9;
int presum[1000009], n;
int main()
{
    cin >> n;
    string s;
    cin >> s;
    s = "&" + s;                 //使字符串下标从1开始
    for (int i = 1; i <= n; i++) //预处理前缀和
    {
        int t = s[i] - '0';
        presum[i] = presum[i - 1] + t;
    }
    for (int i = 1; i <= n; i++) //枚举0，1分界点
    {
        int cur = 0;
        cur += presum[i - 1]; // i前面1的个数 + i后面0的个数
        cur += (n - i - (presum[n] - presum[i]));
        ans = min(ans, cur);
    }
    cout << ans;
}