「题解」「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)|\]
最小。

数据范围

变量数据范围
\(|S|\)\(1\leq |S|\leq 10^6\)

时空限制

题目编号时间限制空间限制
AtCoder – agc045_b\(2\text{s}\)\(1024\text{MiB}\)

题解

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;
}

相关题目