「题解」「agc045_b」01 Unbalanced

AGC045B ，一道神奇的贪心题。

题目链接：AtCoder – agc045_b。

题目

题意

给定一个包含 \(0,1,?\) 的字符串 \(S\)，把所有的 \(?\) 改成 \(0\) 或 \(1\)，使得
\[\max _ {1\leq l\leq r\leq |S|}|\operatorname{cnt}(0)-\operatorname{cnt}(1)|\]
最小。

数据范围

时空限制

题解

AGC045B ，一道神奇的贪心题。

解法 A（暴力）

枚举每一个 \(?\) 是 \(0\) 还是 \(1\)。然后枚举 \(l,r\) 统计答案。

这种做法的时间复杂度为 \(\Theta(2^nn^2)\)。

解法 B（优化暴力）

还是枚举最后的序列，但是我们优化答案的求法。
\[\texttt{ans}=\max _ {1\leq l\leq r\leq n}|\operatorname{cnt}(0)-\operatorname{cnt}(1)|\]

不妨设 \(0\) 的权值为 \(-1\)，\(1\) 的权值为 \(1\)，那么我们定义前缀和数组为 \(\text{sum} _ i\)，则有
\[
\begin{aligned}
\texttt{ans}&=\max _ {1\leq l\leq r\leq n}|\text{sum} _ r-\text{sum} _ {l-1}|\\
&=\max _ {i\in[1,n]}\{\text{sum} _ i\}-\min _ {i\in[1,n]}\{\text{sum} _ {i-1}\}
\end{aligned}
\]

这种做法的时间复杂度为 \(\Theta(2^nn)\)，依然过不了。

解法 C（新的思路）

考虑到推理出答案为
\[\texttt{ans}=\max _ {i\in[1,n]}\{\text{sum} _ i\}-\min _ {i\in[1,n]}\{\text{sum} _ {i-1}\}\]

我们不妨设 \(?\) 一开始全部为 \(1\)，然后我们不难发现，此时 \(\max _ {i\in[1,n]}\{\text{sum} _ i\}\) 是最大的。

我们考虑枚举一个 \(\min\)，表示得到序列的 \(\min _ {i\in[1,n]}\{\text{sum} _ {i-1}\}\) 不得小于 \(\min\)，则可以用贪心的策略缩小 \(\max _ {i\in[1,n]}\{\text{sum} _ i\}\)。

具体地，我们维护原数列的前缀和的后缀最小值为 \(\text{sMin}\)。

当我们从左往右扫描到一个问号时，如果 \(\text{sMin} _ i-\text{base}-2\geq\min\)，那么最大值可以缩小，我们应当缩小（把 \(?\) 从 \(1\) 改成 \(-1\)）。

这种做法需要枚举最小值和扫描数组，时间复杂度为 \(\Theta(n^2)\)，还是不能过。

解法 D（抛弃无用状态）

根据解法 C 的贪心策略，我们不难发现，随着我们枚举的 \(\min\) 的减小，最大值的缩小范围有限。所以如果最大值已经缩到最小以后，\(\min\) 继续减小毫无意义。同时，其他情况下将最小值缩小 \(2\)，与之前的答案之差最多为 \(2\)，也就是枚举更小的最小值其实没有什么用处。考虑奇偶性，只需要检验 \(\text{sMin} _ 1,\text{sMin} _ 1-1\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F

const int MAXS=1000000+5;

int n;
char str[MAXS];
int a[MAXS],sum[MAXS];
int sMin[MAXS];

inline int Solve(reg int Min){
	reg int base=0;
	static int tmp[MAXS];
	for(reg int i=1;i<=n;++i)
		if(str[i]=='?')
			if(sMin[i]-base-2>=Min){
				base+=2;
				tmp[i]=-1;
			}
			else
				tmp[i]=1;
		else
			tmp[i]=(str[i]=='0')?(-1):(1);
	int Max=0,sum=0;
	for(reg int i=1;i<=n;++i){
		sum+=tmp[i];
		Max=max(Max,sum);
	}
	return Max-Min;
}

int main(void){
	scanf("%s",str+1);
	n=strlen(str+1);
	for(reg int i=1;i<=n;++i)
		a[i]=(str[i]=='0')?(-1):(1);
	for(reg int i=1;i<=n;++i)
		sum[i]=sum[i-1]+a[i];
	sMin[n]=sum[n];
	for(reg int i=n-1;i>=0;--i)
		sMin[i]=min(sMin[i+1],sum[i]);
	printf("%d\n",min(Solve(sMin[0]),Solve(sMin[0]-1)));
	return 0;
}

相关题目

• 「题解」「AGC030C」Coloring Torus。