题意：给定一个 01 串，从开头和结尾各删去一些数（可以不删），求 删除的1的个数与剩下的0的个数的最大值的最小值

思路1：思维解法

乍一看虽然没有头绪， 但是仔细一想，既然我要找的是01串中删1数和剩0数中的最大值

那当我们取得最优解时删去的1的个数应该和剩下的0的个数相等，也就是删1数 = 剩0数

我们还能知道删去的数字个数 = 删1数 + 删0数； 易得取最优解时删去的数字个数 = 删0数 + 剩0数；也就是原串中有几个0， 变成最优解就要删去几个数字。

为了保险起见， 我们可以用样例进行验证

101110110 ——> 3个0 ——> 111011——>删1个1， 剩1个0

1001001001001 ——>8个0 ——> 10010删3个1， 剩3个0

0000111111 ——>4个0——>111111——>删0个1， 剩0个0

00000 ——>空串——>不删1不剩0

1111 ——>1111——>不删1不剩0

经过上面的验证， 我们可以得出我们的推断是正确的

那么这个题到这就容易多了

我们不妨把原串中0的个数记为num0。

既然我们变成最优解要删除num0个数字， 而且只能从前和后两边删除。

现在是不是豁然开朗了。

只要从前后两端分别取数， 总数为num0， 找最少包含几个1就可以结束了。

要注意，不能直接暴力枚举，这样会超时的

可以先把0到num0减一的和计算出来，然后每次循环都在前端减一个数，后端加一个数，求最小值就行了，就比如样例1001001001001

1001001001001

1001001001001

1001001001001

......

注：加粗部分为删去的字符

ok，上代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        string a;
        cin >> a;
        int len = a.size();
        int num0= 0;
        for (int i = 0; i < len; i++)
        {
            if (a[i] == '0')
            {
                num0++;
            }
        }
        int cnt = 0;
        for (int i = 0; i < num0; i++)
        {
            cnt += a[i] - '0';
        }
        int minn = cnt;
        for (int i = 0; i < num0; i++)
        {
            cnt += a[len - i - 1] - '0';
            cnt -= a[num0- i - 1] - '0';
            minn = min(minn, cnt);
        }
        printf("%d\n", minn);
    }
    return 0;
}