CodeForces - 645C Enduring Exodus（二分）

109 阅读 0 评论 72 点赞

我是靠谱客的博主温柔洋葱，最近开发中收集的这篇文章主要介绍CodeForces - 645C Enduring Exodus（二分），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://codeforces.com/problemset/problem/645/C

题意：给你n个房间， 0代表空房子， 1代表非空的房子，一个农夫和他的k个牛要住进空房子里面，i房子和j房子的距离是|j-i| 问农夫约翰和他的最远的牛的最小值是多少？

思路：这一题是求最大值的最小值，是一道很明显的二分的题。所以，我们可以枚举每一个空的房间，二分找出农夫住这个房间时与他最远的奶牛的最小值，然后每次更新这个最小值便是答案。最关键的就是这个二分的过程怎么写。对于每一个点，我们可以二分距离，如果这个距离符合题意，我们就可以把这个距离记下来，并令r=mid-1，反之，我们就让l=mid+1。然后用得到的距离来更新答案即可。
具体操作请看代码。

#include<iostream>
#include<cstdio>

using namespace std;

const int maxn=1e5+7;

int sum[maxn];
char a[maxn];
int n,k;

bool check(int i,int dist)
{
    int l=max(1,i-dist);
    int r=min(n,i+dist);
    if(sum[r]-sum[l-1]>=k+1) return true;
    else return false;
}

int Search(int i)
{
    int imin;
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(i,mid))
        {
            imin=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    return imin;
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        scanf("%s",a+1);
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            if(a[i]=='0') sum[i]=sum[i-1]+1;
            else sum[i]=sum[i-1];
        }

        int ans=n;
        for(int i=1; i<=n; i++)
        {
            if(a[i]=='0')
            {
                ans=min(ans,Search(i));
            }
        }
        printf("%dn",ans);
    }
    return 0;
}