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