给一个长度为 nn 的 0101 字符串，你可以任意选择下面两个操作任意次： 从左往右删除任意长度连续段 从右往左删除任意长度连续段 现在要求 max(删掉的1,剩下的0)max(删掉的1,剩下的0) 最小。C++

这是一道贪心题。我们可以先考虑只进行一种操作的情况，即只能从左往右或者从右往左删除。我们可以考虑从两端开始扫描，找到第一个连续的 11 或 00，然后把它们之间的所有 11 或 00 全部删除，保留 11 或 00 中数量更少的那个。然后再继续扫描，直到最终只剩下一个 11 或 00。这个方法可以保证删掉的 11 或 00 数量最小。

但是我们还需要考虑两种操作混合使用的情况。我们可以枚举从左往右删除的段和从右往左删除的段的交点，然后在这个交点处分别进行一次从左往右和从右往左的操作。注意，如果从左往右的段和从右往左的段中间只有一个数字，我们需要把它保留下来，因为它可能是最终的 11 或 00。时间复杂度 O(n^2)O(n
2
)。

C++代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
char s[N];
int main()
{
    cin >> s;
    int n = strlen(s);
    int cnt1 = 0, cnt0 = 0;
    for (int i = 0; i < n; i ++ )
        if (s[i] == '1') cnt1 ++ ;
        else cnt0 ++ ;
    int res = min(cnt0, cnt1);
    for (int i = 0; i < n; i ++ )
        for (int j = i + 1; j < n; j ++ )
        {
            int cnt11 = 0, cnt00 = 0;
            for (int k = i; k <= j; k ++ )
                if (s[k] == '1') cnt11 ++ ;
                else cnt00 ++ ;
            int x = min(cnt11, cnt00);
            for (int k = i; k <= j; k ++ )
                if (s[k] == '1') cnt11 -- ;
                else cnt00 -- ;
            int y = min(cnt1 - cnt11, cnt0 - cnt00);
            res = min(res, x + y);
        }
    cout << res << endl;
    return 0;
}