核心思路：

1. 判断是否已经有序

代码首先通过一个循环 if(ss[i]>ss[i+1]) 遍历字符串，检查是否存在 "10" 这种逆序对。

• 如果 kk == 0，说明整个字符串已经是非递减的（即形如 000...111），无需任何操作，直接输出 0。

2. 字符串下标处理

为了方便前缀和的计算，字符串被改造成了 ss = " " + ss，使其下标从 1 开始到 n 结束 。

特殊情况：首字符为 '1' (ss[1]=='1')

为什么特殊？

如果字符串的第一个字符是 1，那么整个字符串前缀中就不存在 0。这意味着我们无法使用 AND 操作把前面的 1 变成 0（因为没有 0 作为前缀）。

解决思路（全变1）

既然没法变 0，我们唯一的出路就是把后面所有的 0 全都变成 1（通过 OR 操作）。由于第一个字符已经是 1，后面所有的 0 都可以通过 OR 操作一次性变成 1。

代码实现

代码中 d 统计了字符串中 0 的总个数。因此直接输出 num1 = d，代表把所有的 0 变成 1 需要的操作次数。

一般情况：首字符为 '0' (else 分支)

这是代码的核心部分，使用了前缀和 + 枚举分界线的方法。

清空与初始化

循环 for(int i=0;i<=n;i++) p[i]=0, q[i]=0; 用于重置前缀和数组。

构建前缀和数组

• p[i] 记录的是从下标 1 到 i 中，字符 '1' 的个数。
• q[i] 记录的是从下标 1 到 i 中，字符 '0' 的个数。

因为首字符是 '0'，所以我们有底气使用 AND 操作把前面的 1 变成 0。

枚举分界线（寻找最优解）

最终排序好的字符串，一定可以看作是在某个位置 i 切了一刀：i 的左边全变成 0，i 的右边全变成 1。

代码通过 for(int i=1;i<=n;i++) 枚举这条分界线。

• 左边需要的操作次数：把左边所有的 1 变成 0，需要 p[i] 次操作。
• 右边需要的操作次数：把右边所有的 0 变成 1，需要总 0 的个数减去左边 0 的个数，即 q[n] - q[i]。
• 当前分界线总代价：p[i] + q[n] - q[i]。

更新最小值

变量 mx 初始设为极大值 1e9，在循环中不断取 min(mx, p[i] + q[n] - q[i])，找到所有分割点中代价最小的一个。最后输出 mx。

代码：

#include <stdio.h>
#include <string.h>

#define MAXN 200209

long long p[MAXN];
long long q[MAXN];
char ss[MAXN];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int kk = 0;
        scanf("%s", ss + 1);  /* 下标从 1 开始读入 */

        for (int i = 1; i <= n - 1; i++) {
            if (ss[i] > ss[i + 1]) {
                kk = 1;
                break;
            }
        }

        if (kk == 0) {
            printf("0\n");
        } else {
            long long num1 = 1000000000LL;
            if (ss[1] == '1') {
                long long d = 0;  /* 全变 1 的代价：0 的个数 */
                for (int i = 1; i <= n; i++) {
                    if (ss[i] == '0') {
                        d++;
                    }
                }
                num1 = d;
                printf("%lld\n", num1);
            } else {
                for (int i = 0; i <= n; i++) {
                    p[i] = 0;
                    q[i] = 0;
                }
                for (int i = 1; i <= n; i++) {
                    if (ss[i] == '1') {
                        p[i] = p[i - 1] + 1;
                        q[i] = q[i - 1];
                    } else {
                        q[i] = q[i - 1] + 1;
                        p[i] = p[i - 1];
                    }
                }
                long long mx = 1000000000LL;
                for (int i = 1; i <= n; i++) {
                    long long cur = p[i] + q[n] - q[i];
                    if (cur < mx) mx = cur;
                }
                printf("%lld\n", mx);
            }
        }
    }
    return 0;
}