题解：CF2266C AND, OR, Sort!

· · 题解

解题思路

容易想到若要令修改后的字符串 s 单调不降，则其一定为前半段是 0，后半段是 1 的形式。

然后思考 OR 和 AND 的性质，能够发现：

也就是说，若 s_1 是 0 则后续所有 1 都能修改为 0，此时枚举 01 交界点是一定可行的（这时你可能会有个疑问，那么如果 s 全为 0 怎么办？我们暂且先不管）；若 s_1 是 1，则后续只能全部是 1，这里需要特判。

我们先预处理前缀 1 的个数，后缀 0 的个数。

若 s_1 为 1，则答案就是 suf_1，因为 s_1 一定不为 0。

若 s 全是 0，则遍历到 s_n 时的后缀为 0，前缀为 0，也能通过取最小值得到正确答案（此处前后缀含义省略）。

剩下的情况都围绕“枚举 01 交界点，将左侧所有 1 改成 0，将右侧所有 0 改成 1”的思路直接模拟即可，这时候你就知道为什么要预处理前后缀了。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int pre[N], suf[N]; // 前/后缀 1/0的个数

void solve() {
    int n; string s;
    cin >> n >> s;
    s = ' ' + s; // 把下标转成 1-base
    pre[0] = suf[n + 1] = 0; // 别忘了初始化
    for (int i = 1; i <= n; ++i) 
        pre[i] = pre[i - 1] + (s[i] == '1');
    for (int i = n; i >= 1; --i)
        suf[i] = suf[i + 1] + (s[i] == '0');
    if (s[1] == '1') return cout << suf[1] << '\n', void();
    int ans = 1e9;
    for (int i = 1; i <= n; ++i) 
        ans = min(ans, pre[i - 1] + suf[i + 1]);
    cout << ans << '\n';
}

int main( ) {
    int T; cin >> T;
    while (T--) solve();
    return 0;
}