【打CF，学算法——三星级】CodeForces 645C Enduring Exodus （二分+贪心）

提交链接：CF 645C

题面：

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.

ExamplesInput

7 2
0100100

Output

Input

5 1
01010

Output

Input

3 2
000

Output

Note

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

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

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 is1.

--------------------------------------------------------------------------------------啦啦啦，我是分割线--------------------------------------------------------------------------------------------------------------

题意：

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

思路：

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

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using 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<=ri)
   {
   int mid=(le+ri)>>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("%d\n",ans);
return 0;
}

秒客网

【打CF，学算法——三星级】CodeForces 645C Enduring Exodus （二分+贪心）

相关文章