C++(clang++11) 解法, 执行用时: 80ms, 内存消耗: 632K, 提交时间: 2021-01-02 09:51:12

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
pair<int,int>pre[maxn], suf[maxn];
int main(){
	int n;
	string st;
	cin >> n >> st;
	int a = 0, b = 0;
	for(int i = 0; i < n; i++){
		if(st[i] == '0')b++;
		else{
			if(b)b--;
			else a++; 
		}
		pre[i]={a,b};
    }
    a = b = 0;
	for(int i = n-1; i >= 0; i--){
		if(st[i] == '0'){
			if(a)a--;
			else b++;
		}else{
			a++;
		}
		suf[i] = {a,b};
	}
	int ans = pre[n-1].first + pre[n-1].second;
	for(int i = 0; i < n; i++){
		a = b = 0;
		for(int j = i; j < n; j++){
			if(st[j] == '0')a++;
			else b++;
			if(b == 2*a){
				int a1 = i?pre[i-1].first:0;
				int b1 = i?pre[i-1].second:0;
				int a2 = suf[j+1].first;
				int b2 = suf[j+1].second;
				ans = min(ans, a1+b2+abs(b1-a2));
			} 
		}
	}
	cout << ans << endl;
}