利用二分法求解

題意：

??? 一個(gè)農(nóng)夫帶著k頭牛去住店，（人一間，每牛一間）已知該旅店共有n間房，其中部分房間已有人住，房間住宿情況由01串表示，0表示空，1表示已有人住，剩余房間足夠容納(k+1)頭牛/人。為了保障牛的安全，希望人住的房間離最遠(yuǎn)的牛的房間位置盡量小，輸出最小距離。

思路：

??? 很明顯為了讓人住的離最遠(yuǎn)的牛最近，那么最后這批人牛住的房間肯定是連續(xù)的（不算原有的住宿人員），且人住的位置離中心點(diǎn)越近越好。首先，枚舉住宿的左區(qū)間，如果左端點(diǎn)已有人住，則跳過(guò)該點(diǎn)，如果空，則二分以該點(diǎn)為左端點(diǎn)，空閑房間數(shù)為k+1的最左位置。隨后在這個(gè)區(qū)間內(nèi)，開(kāi)始尋找空閑的最中心位置（距離遠(yuǎn)的那端盡量?。脜^(qū)間長(zhǎng)度奇偶性設(shè)置兩個(gè)指針p1,p2的初始位置，隨后分別往兩端移動(dòng)，因?yàn)橐欢ㄓ锌臻e位置，且兩指針同時(shí)移動(dòng)，不會(huì)出現(xiàn)越界情況。最后找到一個(gè)解，則計(jì)算最遠(yuǎn)距離，若小于最優(yōu)值，則更新。

代碼：

#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;
	}
	//設(shè)置一個(gè)肯定會(huì)被更新的最大值
	ans=10e6;
	for(int?i=1;i<=n;i++)
	{
		//該點(diǎn)已有人住
	???if(room[i]==room[i-1])
		???continue;
???????le=i;
	???ri=n;
	???border=-1;
	???//二分右區(qū)間
	???while(le>1;
		???if(room[mid]-room[i-1]>k)
		???{

			???border=mid;
			???ri=mid-1;
		???}
		???else
			???le=mid+1;
	???}
	???//如果能找到k+1個(gè)房間
	???if(border!=-1)
	???{
?????????int?len=(border-i),p1,p2;
		?//根據(jù)區(qū)間長(zhǎng)度奇偶性，設(shè)置p1,p2
?????????if(len%2)
		?{
			?p1=(border+i)>>1;
			?p2=(border+i)/2+1;
		?}
		?else
		?{
			?p1=p2=(border+i)>>1;
		?}
		?//尋找最先出現(xiàn)空閑房間
		?while(1)
		?{
			?if((room[p1]!=room[p1-1]))
		????{
				pos=p1;
				break;
			}
			?else?if(room[p2]!=room[p2-1])
			?{
				?pos=p2;
				?break;
			}
			?p1--;
			?p2++;
		?}
?????????//更新最優(yōu)值
		?ans=min(ans,max(pos-i,border-pos));
	???}
	???//說(shuō)明剩下，已無(wú)可能有k+1個(gè)房間
	???else
		???break;
	}
	printf("%dn",ans);
	return?0;
}