CodeForces 645C Enduring Exodus

枚举，三分。

首先，这$n+1$个人一定是连续的放在一起的。可以枚举每一个起点$L$，然后就是在$[L,R]$中找到一个位置$p$，使得$p4最优，因为越往两边靠，距离就越大，在中间某位置取到最优解，所以三分一下就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-6;
void File()
{
    freopen("D:\in.txt","r",stdin);
    freopen("D:\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c=getchar(); x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
}

const int maxn=100010;
int n,k,p[maxn],sz;
char s[maxn];

int get(int x,int low,int high)
{
    return max(p[x]-p[low],p[high]-p[x]);
}

int f(int L,int R)
{
    int t1,t2; int low=L,high=R;
    for(int i=1;i<=200;i++)
    {
        t1=(low+high)/2;
        t2=(t1+high)/2;
        if (get(t1,L,R)<get(t2,L,R)) high=t2;
        else low=t1;
    }
    return get(t1,L,R);
}


int main()
{
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    for(int i=0;s[i];i++)
    {
        if(s[i]=='1') continue;
        sz++; p[sz]=i+1;
    }

    int ans=200000;
    for(int i=1;i<=sz;i++)
    {
        if(i+k>sz) break;
        ans=min(ans,f(i,i+k));
    }
    printf("%d
",ans);
    return 0;
}