【打CF，學(xué)算法——三星級】CodeForces 645C Enduring Exodus （二分+貪心）

【CF簡介】

提交鏈接：CF 645C

題面：

C. Enduring Exodus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

In an attempt to escape the Mischievous Mess Makers' antics, Farmer John has abandoned his farm and is traveling to the other side of Bovinia. During the journey, he and hisk cows have decided to stay at the luxurious Grand Moo-dapest Hotel. The hotel consists ofn rooms located in a row, some of which are occupied.

Farmer John wants to book a set of k?+?1 currently unoccupied rooms for him and his cows. He wants his cows to stay as safe as possible, so he wishes to minimize the maximum distance from his room to the room of his cow. The distance between rooms i and j is defined as |j?-?i|. Help Farmer John protect his cows by calculating this minimum possible distance.

Input

The first line of the input contains two integers n andk (1?≤?k?<?n?≤?100?000)?— the number of rooms in the hotel and the number of cows travelling with Farmer John.

The second line contains a string of length n describing the rooms. Thei-th character of the string will be '0' if thei-th room is free, and '1' if thei-th room is occupied. It is guaranteed that at leastk?+?1 characters of this string are '0', so there exists at least one possible choice ofk?+?1 rooms for Farmer John and his cows to stay in.

Output

Print the minimum possible distance between Farmer John's room and his farthest cow.

Examples Input

7?2
0100100

Output

2

Input

5?1
01010

Output

2

Input

3?2
000

Output

1

Note

In the first sample, Farmer John can book room 3 for himself, and rooms 1 and 4 for his cows. The distance to the farthest cow is 2. Note that it is impossible to make this distance 1, as there is no block of three consecutive unoccupied rooms.

In the second sample, Farmer John can book room 1 for himself and room 3 for his single cow. The distance between him and his cow is 2.

In the third sample, Farmer John books all three available rooms, taking the middle room for himself so that both cows are next to him. His distance from the farthest cow is 1.

--------------------------------------------------------------------------------------啦啦啦，我是分割線--------------------------------------------------------------------------------------------------------------

題意：

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

思路：

??? 很明顯為了讓人住的離最遠的牛最近，那么最后這批人牛住的房間肯定是連續(xù)的（不算原有的住宿人員），且人住的位置離中心點越近越好。首先，枚舉住宿的左區(qū)間，如果左端點已有人住，則跳過該點，如果空，則二分以該點為左端點，空閑房間數(shù)為k+1的最左位置。隨后在這個區(qū)間內(nèi)，開始尋找空閑的最中心位置（距離遠的那端盡量?。脜^(qū)間長度奇偶性設(shè)置兩個指針p1,p2的初始位置，隨后分別往兩端移動，因為一定有空閑位置，且兩指針同時移動，不會出現(xià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è)置一個肯定會被更新的最大值
	ans=10e6;
	for(int?i=1;i<=n;i++)
	{
		//該點已有人住
	???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個房間
	???if(border!=-1)
	???{
?????????int?len=(border-i),p1,p2;
		?//根據(jù)區(qū)間長度奇偶性，設(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));
	???}
	???//說明剩下，已無可能有k+1個房間
	???else
		???break;
	}
	printf("%dn",ans);
	return?0;
}