题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的字符串长度之和$\leq 2 \times 10^5$。

每组数据输入长度$\leq 2 \times 10^5$的字符串$s$，只包含$0$和$1$。

选择$s$的一个子串（可以为空），设$in_0$是子串内的$0$的个数，$out_1$是子串外的$1$的个数。

定义子串的代价为$max(in_0, out_1)$。

输出代价的最小值。

注：子串是连续的。

输入样例

5
101110110
1001001001001
0000111111
00000
1111

输出样例

1
3
0
0
0

算法

三分

先做个前缀和的预处理，得到前缀和数组$s_0$和$s_1$，$s_0[i]$表示子串$s[1:i]$中$0$的数量，$s_1[i]$表示子串$s[1:i]$中$1$的数量。然后枚举子串的左端点$i \in [1,n]$，计算以$i$为左端点的所有子串中，代价的最小值。根据代价的定义我们可以知道，当左端点固定时，这个子串越长$in_0$越大，越短则$out_1$越大，是存在单调性的。

定义目标函数$|in_0-out_1|$，直觉上感觉应该会存在一个最小值点，使得目标函数先随子串的长度增加而减小，到达最小值点后再增加。因此，这样的单峰函数就可以用三分来求最值（求$|in_0-out_1|$的最小值）。当三分到区间中只剩下三个候选的子串右端点时，遍历一下求得以$i$为子串左端点的代价最小值即可。所有$i$位置的答案最小值，就是我们最终要求的所有子串的最小代价。

复杂度分析

时间复杂度

遍历所有子串的左端点$i$的时间复杂度为$O(n)$，三分的时间复杂度为$O(logn)$，因此算法整体的时间复杂度为$O(nlogn)$。

空间复杂度

空间消耗的瓶颈在于前缀和数组$s_0$和$s_1$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
char s[N];
int s0[N], s1[N];

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for(int i = 1; i <= n; i++) {
            s0[i] = s0[i - 1] + (s[i] == '0'? 1: 0);
            s1[i] = s1[i - 1] + (s[i] == '1'? 1: 0);
        }
        int ans = 1<<30;
        for(int i = 1; i <= n; i++) {
            int l = i, r = n;
            ans = min(ans, s1[n]);      // 初始化答案为子串为空串时的代价
            while(r - l > 3) {
                int m1 = l + (r - l)/3;
                int m2 = l + (r - l)*2/3;
                int f1 = abs(s0[m1] - s0[i - 1] - (s1[i - 1] + s1[n] - s1[m1]));
                int f2 = abs(s0[m2] - s0[i - 1] - (s1[i - 1] + s1[n] - s1[m2]));
                if(f1 > f2) {
                    l = m1;
                }else {
                    r = m2;
                }
            }
            for(int k = l; k <= r; k++) {
                ans = min(ans, max(s0[k] - s0[i - 1], s1[i - 1] + s1[n] - s1[k]));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}