CodeForces 645 C.Enduring Exodus（水~）

Description
一排n个屋子，0表示屋子是空的，1表示屋子被占了，现在要选k个空屋子放牛，一个空屋子待人，最小化人和牛的距离最大值
Input
第一行两个整数n和k表示屋子数和牛数，之后一个长度为n的01串表示每个屋子的占用情况(1<=k < n<=1e5)
Output
输出最小化后的人牛距离最大值
Sample Input
7 2
0100100
Sample Output
2
Solution
必然要选择连续k+1个0（被1隔开也算连续，被0隔开则不连续），然后把人放在尽可能中间的房子，记录所有0的位置，a[i]表示第i个0的位置，每次在a[i]和a[i+k]中二分查找最接近a[i]+(a[i-k]-a[i])/2的点pos作为人的位置然后取所有max(a[i+k]-pos,pos-a[i])中的最小值即为答案
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 111111
int n,k,a[maxn];
char s[maxn];
int main()
{
while(~scanf("%d%d",&n,&k))
{
scanf("%s",s+1);
int res=0;
for(int i=1;i<=n;i++)
if(s[i]=='0')a[res++]=i;
int ans=n;
for(int i=0;i<res-k;i++)
{
int dis=a[i+k]-a[i];
int pos=lower_bound(a,a+res,a[i]+dis/2)-a;
ans=min(ans,max(a[i+k]-a[pos],a[pos]-a[i]));
pos--;
ans=min(ans,max(a[i+k]-a[pos],a[pos]-a[i]));
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是专注朋友为你收集整理的CodeForces 645 C.Enduring Exodus（水~）的全部内容，希望文章能够帮你解决CodeForces 645 C.Enduring Exodus（水~）所遇到的程序开发问题。

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