首先可以假定整个序列 \(c_0\ge c_1\)，否则我们把 \(0\) 变成 \(1\)，\(1\) 变成 \(0\)，并翻转序列。新序列答案与原序列相同。
结论：仅操作 \(c_0=c_1\) 的区间的最小答案和原题一致。
证明：考虑操作了一个 \(c_0-c_1=d\) 的区间。区间第一个数，若是 \(0\)，那我们的操作区间其实不应该包含它。也就是说第一个数是 \(1\)，那么我们找到一个 \(1\) 和 \(0\) 数量相等的前缀将其排序，第一个数就变成了 \(0\)。然后我们把它去掉，就花费了 \(1\) 的代价进入了 \(d-1\) 的子问题，直到 \(d=0\) 可以一次性排序。这就相当于把原操作拆成了 \(d+1\) 个 \(c_0=c_1\) 的操作。
得知这个结论以后，就可以考虑贪心了。
贪心策略：每次操作一个最长的 \(c_0=c_1\) 的前缀，然后把其中的 \(0\) 删掉。若此时 \(c_0\le c_1\) 了，就可以从删掉的 \(0\) 里面补回来一些，然后一次排好，否则重复此过程。
正确性可以感性理解，在最后一次操作前，前 \(c_0-c_1\) 个数应当全是 \(0\)。那么第一个 \(1\) 肯定是需要往后，而且肯定是越早越好。
具体实现，我们求出 \(mx_i\) 表示最大使得每个前缀中 \(0\) 比 \(1\) 多 \(i\) 个的位置。就可以在每次删掉若干个 \(0\) 后求出下一段 \(01\) 个数相等的最长前缀了。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int T;
int n;
int a[N]; char s[N];
int mx[N];
void solve() {
scanf("%d%s", &n, s);
int c0 = 0, c1 = 0;
for (int i = 0; i < n; ++i) a[i] = s[i] - '0', c0 += a[i] == 0;
c1 = n - c0;
if (!c1) return printf("%d\n", 0), void();
for (int i = 0; i < n; ++i) {
bool flag = 1;
if (a[i] == 1) {
for (int j = i + 1; j < n; ++j) flag &= a[j];
if (flag) return printf("%d\n", 0), void();
break;
}
}
if (c0 < c1) {
swap(c0, c1), reverse(a, a + n);
for (int i = 0; i < n; ++i) a[i] ^= 1;
}
memset(mx, 0, sizeof (int) * (n + 1));
for (int i = 0, cur = 0; i < n; ++i) {
if (a[i]) --cur; else ++cur;
if (cur >= 0) mx[cur] = i;
}
int delta = c0 - c1, cur = 0;
while (a[cur] == 0 && cur < n) ++cur;
int ans = 0;
while (cur < delta) {
++ans;
cur += (mx[cur] - cur + 1) / 2;
}
printf("%d\n", ans + 1);
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}