利用二分法求解

题意：

    一个农夫带着k头牛去住店，（人一间，每牛一间）已知该旅店共有n间房，其中部分房间已有人住，房间住宿情况由01串表示，0表示空，1表示已有人住，剩余房间足够容纳(k+1)头牛/人。为了保障牛的安全，希望人住的房间离最远的牛的房间位置尽量小，输出最小距离。

思路：

    很明显为了让人住的离最远的牛最近，那么最后这批人牛住的房间肯定是连续的（不算原有的住宿人员），且人住的位置离中心点越近越好。首先，枚举住宿的左区间，如果左端点已有人住，则跳过该点，如果空，则二分以该点为左端点，空闲房间数为k+1的最左位置。随后在这个区间内，开始寻找空闲的最中心位置（距离远的那端尽量小），利用区间长度奇偶性设置两个指针p1,p2的初始位置，随后分别往两端移动，因为一定有空闲位置，且两指针同时移动，不会出现越界情况。最后找到一个解，则计算最远距离，若小于最优值，则更新。

代码：

#include#include#include#includeusing namespace std;
char s[100010];
int room[100010];
int main()
{
    int n,k,len,le,ri,border,ans,pos;
	//读入
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	room[0]=0;
	for(int i=1;i<=n;i++)
	{
		//前缀和
		if(s[i-1]-'0')
			room[i]=room[i-1];
		else
			room[i]=room[i-1]+1;
	}
	//设置一个肯定会被更新的最大值
	ans=10e6;
	for(int i=1;i<=n;i++)
	{
		//该点已有人住
	   if(room[i]==room[i-1])
		   continue;
       le=i;
	   ri=n;
	   border=-1;
	   //二分右区间
	   while(le>1;
		   if(room[mid]-room[i-1]>k)
		   {

			   border=mid;
			   ri=mid-1;
		   }
		   else
			   le=mid+1;
	   }
	   //如果能找到k+1个房间
	   if(border!=-1)
	   {
         int len=(border-i),p1,p2;
		 //根据区间长度奇偶性，设置p1,p2
         if(len%2)
		 {
			 p1=(border+i)>>1;
			 p2=(border+i)/2+1;
		 }
		 else
		 {
			 p1=p2=(border+i)>>1;
		 }
		 //寻找最先出现空闲房间
		 while(1)
		 {
			 if((room[p1]!=room[p1-1]))
		    {
				pos=p1;
				break;
			}
			 else if(room[p2]!=room[p2-1])
			 {
				 pos=p2;
				 break;
			}
			 p1--;
			 p2++;
		 }
         //更新最优值
		 ans=min(ans,max(pos-i,border-pos));
	   }
	   //说明剩下，已无可能有k+1个房间
	   else
		   break;
	}
	printf("%dn",ans);
	return 0;
}