CodeForces - 645C（最大化最小值问题 二分）

题意：农夫带着他的牛们离家出走了（为什么农夫一定要和牛联系在一起？？？），他们到了一个旅店，旅店房间状况通过一个01串告诉你，0代表空的，1代表被占了，问怎么安排住宿可以使牛离农夫的最远距离最小。

题解：通过前缀和处理出某个位置之前的0的个数，然后二分枚举对于位置i的左右两边可以放置下所有牛的最小距离。然后输出最小的那个一个就可以了。

没怎么接触过这种题，好像小白上面有，当初看小白的时候二分部分没怎么自习研究。Mark一下。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f;
int pre[100005],n,m;
char x[100005];
bool check(int pos,int dis)
{
int l = max(pos - dis,1);
int r = min(pos + dis,n);
return pre[r] - pre[l-1] >= m + 1;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
scanf("%s",x+1);
memset(pre,0,sizeof pre);
for (int i = 1; i <= n; i++)
{
if(x[i] == '0')
pre[i] = pre[i - 1] + 1;
else pre[i] = pre[i - 1];
}
int l,r,mid,ans = inf;
for (int i = 1; i <= n; i++)
{
if(x[i] == '1')continue;
l = 1,r = n;
while(l < r)
{
mid = (l + r)>>1;
if(check(i,mid))
{
r = mid;
}
else l = mid + 1;
}
ans = min(ans,r);
}
printf("%dn",ans);
}
}

最后

以上就是活力白昼为你收集整理的CodeForces - 645C（最大化最小值问题 二分）的全部内容，希望文章能够帮你解决CodeForces - 645C（最大化最小值问题 二分）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。