Educational Codeforces Round 128 (Rated for Div. 2)

比赛链接：

https://codeforces.com/contest/1680

C. Binary String

题目大意：

给定一个二进制字符串，可以从头部和尾部删除一个子串，最后的价值为删除的 1 的数量和剩下的 0 的数量的最大值，问这个价值最小是多少。

思路：

考虑暴力做法，枚举剩下的字符串的起点和终点，\(O(n^2)\)，超时。
如果固定了左端点，可以发现右端点的移动对答案的影响是单调的，当右端点向右移动时，剩下的 0 的数量增加，删除的 1 的数量减少，向左移动时，剩下的 0 的数量减少，删除的 1 的数量增加。可以通过二分求答案。

也可以固定右端点，通过双指针移动，当左指针向右移动时，删除的 1 的数量增加，剩下的 0 的数量减少，右指针向右移动时，删除的 1 的数量减少，剩下的 0 的数量增加，当二者达到平衡的时候，就是值最小的时候。

二分

#include
using namespace std;
int T;
string s;
void solve(){
	cin >> s;
	int n = s.size(), ans = n + 1, sum = 0;
	vector  cnt0(n + 1, 0), cnt1(n + 1, 0);
	for (int i = 0; i < n; i ++ ){
		cnt0[i + 1] = cnt0[i] + (s[i] == '0');
		cnt1[i + 1] = cnt1[i] + (s[i] == '1');
		sum += (s[i] == '1');
	}
	ans = min(ans, cnt1[n] - cnt1[0]);
	for (int i = 0; i < n; i ++ ){
		int l = i, r = n;
		while (l < r){
			int mid = l + r >> 1;
			int a = sum - (cnt1[mid + 1] - cnt1[i]), b = cnt0[mid + 1] - cnt0[i];
			if (a >= b){
				ans = min(ans, max(a, b));
				l = mid + 1;
			}
			else r = mid;
		}
	}
	cout << ans << "\n";
}
int main(){
	cin >> T;
	while (T -- )
		solve();
	return 0;
}

双指针

#include
using namespace std;
int T;
string s;
void solve(){
	cin >> s;
	int n = s.size(), ans = n + 1, sum = 0;
	vector  cnt0(n + 1, 0), cnt1(n + 1, 0);
	for (int i = 0; i < n; i ++ ){
		cnt0[i + 1] = cnt0[i] + (s[i] == '0');
		cnt1[i + 1] = cnt1[i] + (s[i] == '1');
		sum += (s[i] == '1');
	}
	ans = min(ans, cnt1[n] - cnt1[0]);
	for (int l = 0, r = 0; r < n; ){
		while (l < r && sum - (cnt1[r + 1] - cnt1[l]) < cnt0[r + 1] - cnt0[l])
			l ++ ;
		ans = min(ans, max(sum - (cnt1[r + 1] - cnt1[l]), cnt0[r + 1] - cnt0[l]));
		r ++ ;
	}
	cout << ans << "\n";
}
int main(){
	cin >> T;
	while (T -- )
		solve();
	return 0;
}