[code source] daily one question non decreasing 01 sequence

Topic link ： Non decreasing 01 Sequence - subject - Daimayuan Online Judge

Topic

huaji There is one 01 Sequence , You can negate one of them every time （0 change 1,1 change 0）

Finding at least a few bits can make the sequence become The decreasing Sequence

Input format

Enter an integer in the first line  n (1≤n≤10^6)

On the second line, enter a length of n And only 0 and 1 String

Output format

Output an integer , Is the minimum number of operations that the sequence becomes a non decreasing sequence

sample input

6
010110

sample output

2

analysis ： 

Non decreasing sequence , Isn't it incremental , Consider that the last substring is 00……11…… This form , It is made up of continuous 0 And continuous 1 constitute , So let's consider enumeration 0 and 1 The dividing point of , The number of operations is in front of the dividing point 1 The number of （1 Must become 0） After the dividing point 0 The number of （0 It has to be 1）.

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
int ans = 1e9;
int presum[1000009], n;
int main()
{
    cin >> n;
    string s;
    cin >> s;
    s = "&" + s;                 // Subscript string from 1 Start 
    for (int i = 1; i <= n; i++) // Preprocessing prefixes and 
    {
        int t = s[i] - '0';
        presum[i] = presum[i - 1] + t;
    }
    for (int i = 1; i <= n; i++) // enumeration 0,1 Dividing point 
    {
        int cur = 0;
        cur += presum[i - 1]; // i front 1 The number of  + i Back 0 The number of 
        cur += (n - i - (presum[n] - presum[i]));
        ans = min(ans, cur);
    }
    cout << ans;
}