为什么二分 80pts?
查看原帖
为什么二分 80pts?
93266
断清秋楼主2022/1/24 21:31

运用归纳法证明,显然可以知道 ansans 在偶数序列上有单调性。为什么二分会 WA?

int main()
{
	freopen("s1.in","r",stdin);
	freopen("s1.ans","w",stdout);
	n=read();
	for(ri i=1;i<=n;i++)
		a[i]=read();
	for(ri i=1;i<=n;i++)
		if(a[i]==0)
			sum0[i]=sum0[i-1]+1,sum1[i]=sum1[i-1];
		else
			sum1[i]=sum1[i-1]+1,sum0[i]=sum0[i-1];
	int l=0,r=2*min(sum1[n],sum0[n]),mid=(l+r)/2;
	while(l<r)
	{
		mid=(l+r)/2;
		if(mid%2)
			mid++;
		cout<<2222<<" "<<mid<<"\n"; 
		bool flag=0;
		for(ri i=1;i<=n-mid+1;i++)
			if(sum1[i+mid-1]-sum1[i-1]==sum0[i+mid-1]-sum0[i-1])
			{
				flag=1;
				break;
			}
		if(flag==1)
			l=mid;
		else
			r=mid-2;
	}
	cout<<r<<"\n";
	back 0;
}
2022/1/24 21:31
加载中...