【hpu 1016 985的0-1串难题 [二分、尺取]】

点击打开链接

AC代码：

#include<cstdio>
#include<cstring>
char s[100010];
int table[100010];
int n,k;
void Check()
{
	memset(table,0,sizeof(table));
	if(s[0]=='0')
		table[0]=1;
	for(int i=1;i<n;i++)
		if(s[i]=='0')
			table[i]=table[i-1]+1;
		else
			table[i]=table[i-1];
 } 
bool Judge(int x)
{
	int size=n-x;
	for(int i=0;i<=size;i++)
	{
		int temp=0;
		if(s[i]=='0')
			temp++;
		if(table[i+x-1]-table[i]+temp<=k)
			return true;
	}
	return false;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		scanf("%s",s);
		Check();
		int ans,mid,l=1,r=n;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(Judge(mid))
			{
				ans=mid;
				l=mid+1;
			}
			else
				r=mid-1;
		}
		printf("%d\n",ans);
	}
	return 0;
}