NC222503. [USACOOpen2020B]SocialDistancingI
描述
输入描述
The first line of input contains N. The next line contains a string of length N of 0s and 1s describing the sequence of stalls in the barn. 0s indicate empty stalls and 1s indicate occupied stalls. The string has at least two 0s, so there is at least enough room for two new cows.
输出描述
Please print the largest value of D (the closest distance between two occupied stalls) that Farmer John can achieve after adding his two new cows in an optimal fashion.
示例1
输入:
14 10001001000010
输出:
2
说明:
In this example, Farmer John could add cows to make the occupancy string look like 10x010010x0010, where x's indicate the new cows. In this case D=2. It is impossible to add the new cows to achieve any higher value of D.C++ 解法, 执行用时: 6ms, 内存消耗: 656K, 提交时间: 2022-03-28 20:59:16
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int w[N];
string p;
int n,cnt;
bool check(int x)
{
int sum=0;
int tmp=0-x;
for(int i=1;i<=cnt;i++)
{
while(tmp+2*x<=w[i])
{
tmp+=x;
sum++;
}
tmp=w[i];
}
while(tmp+x<n)
{
tmp+=x;
sum++;
}
if(sum>=2) return 1;
else return 0;
}
int main()
{
cin>>n;
cin>>p;
for(int i=0;i<p.size();i++)
{
if(p[i]=='1')
{
w[++cnt]=i;
}
}
int l=1,r=1e9;
for(int i=1;i<cnt;i++)
{
r=min(w[i+1]-w[i],r);
}
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}