Occupy the Cities

Occupy the Cities"/>

Occupy the Cities

 分析：

        分析每一个0的位置，记录每一个0距离两侧的1的最近距离，每一个1要么向左扩展要么向右扩展，可以将扩展过的1标记，如果需要向另一侧扩展，那么必须满足距离另一侧的0的距离加1小于等于时间，比如0100第一个0使1向左扩展并且标记了1，第二个和第三个0需要1向右扩展，因此需要1多一步用来向右扩展，使0100变成0110，然后就可以双向扩展，二分最小的时间，每次判断每一个0是否满足可以双向扩展，如果不可以在判断是否满足向左扩展，如果再不满足在判断是否可以向右扩展，如果都不可以就返回false,否则返回true。判断在时间内满不满足只需要比较时间和距离最近的1的距离大小。

代码：

#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int,int> pii;const int N=1e6+10;int le[N];
int ri[N];
int n;
string s;
bool st[N];bool check(int mid)
{for(int i=0;i<n;i++) st[i]=false;for(int i=0;i<n;i++){if(s[i]=='1') continue;int  d=min(i-le[i],ri[i]-i)+1;if(d<=mid) continue;if(le[i]>=0&&!st[le[i]]&&i-le[i]<=mid){st[le[i]]=true;continue;}if(ri[i]<n&&!st[ri[i]]&&ri[i]-i<=mid){st[ri[i]]=true;continue;}return false;}return true;
}int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _;cin>>_;while(_--){cin>>n;cin>>s;int last=-1e9;for(int i=0;i<n;i++){if(s[i]=='1') last=i;else le[i]=last;}last=1e9;for(int i=n-1;i>=0;i--){if(s[i]=='1') last=i;else ri[i]=last;}int l=0;int r=n-1;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<'\n';}
}