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; }
近期评论