• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AGC045B 01 Unbalanced

开发技术 开发技术 6天前 8次浏览

有个01序列,其中有些位置不确定。你要确定这些位置,最小化最大的区间0和1出现次数的差的绝对值。

(nle 10^6)


把01分别看成(pm 1)。显然可以前缀和之后转化成最大值减最小值之差。

(F(M))表示最大值不超过(M)时,最小值最大是多少。求出(Z)表示最小的可能的最大前缀和,把所有不确定位置都取(-1)可得。可以贪心求出(F(M)):先一开把所有的不确定位置变成(-1),从前往后扫,如果当前位置调成(1)后面的最大值依然不超过(M),那么就调成(1)。最后(min_{Mge Z} M-F(M))就是答案。这是(O(n^2))的做法。

可以优化:考虑(F(M))(F(M+2))的变化。在做(F(M))的过程中,第一次遇到把不确定位置调成(1)就会超过(M)的位置,在这里做(F(M+2))的过程中能够调成(1),然后因为已经给后缀全体加(2)所以剩下的和做(F(M))时一样。如果最小值在这个位置后面,就顶多会加(2)。因此有(F(M)+2ge F(M+2)),也就是(F(M)-Mge F(M+2)-(M+2))

于是只需要算(F(Z))(F(Z+1))。时间(O(n))


using namespace std;
#include <bits/stdc++.h>
#define N 1000005
char str[N];
int n,a[N],s[N];
int suc[N];
int calc(int lim){
	int c=0,res=0;
	for (int i=1;i<=n;++i){
		if (a[i]==0){
			if (suc[i]+c+2<=lim)
				c+=2;
		}
		res=min(res,s[i]+c);
	}
	return res;
}
int main(){
	freopen("in.txt","r",stdin);
	scanf("%s",str+1);
	n=strlen(str+1);
	for (int i=1;i<=n;++i)
		a[i]=(str[i]=='0'?1:str[i]=='1'?-1:0);
	int mx=0;
	for (int i=1;i<=n;++i)
		s[i]=s[i-1]+(a[i]<=0?-1:1),mx=max(mx,s[i]);
	suc[n]=s[n];
	for (int i=n-1;i>=1;--i)
		suc[i]=max(suc[i+1],s[i]);
	int ans=min(mx-calc(mx),mx+1-calc(mx+1));
	printf("%dn",ans);
	return 0;
}

程序员灯塔
转载请注明原文链接:AGC045B 01 Unbalanced
喜欢 (0)