2021桂林-Occupy the Cities-(思维+二分答案)

G

题意：
就是给你一个长度为n的01串，然后有些地方是1，有些地方是0，每次为1的可以往左或者往右扩展一个，现在问你最少多少秒，所有的都变成了1。

思考：
刚看到这题的时候，就是在想贪心，看到答案最小，要么是dp？或者二分，dp的话感觉状态方程不好写，二分的话check判断的时候你得拿一个最优的方案去求出来时间把，如果你知道最优的方案了直接就求出来答案了，又不行了，然后就陷入傻逼的贪心去了。这种题一看贪心就不行啊，直接一遍肯定错。直到后期，我感觉只能二分了，突然想到，一个0要么被左边的1占领，要么是右边的，那么就二分mid，如果每个0需要的时间都<=mid肯定可以的。但是样例有个没过，实际上就是有的地方的0需要他旁边的1第一次就往它这边扩，如果需要的话就尽量用左边的1，因为右边的1要留给后面的。如果都不能用了，或者用了也比mid大那么就return false。
反正看到最小的答案，要么贪心要么dp要么二分，往往二分的可能性最大，check就去用暴力贪心，往往可以解决问题。脑子灵活一点呀。

代码：

int T,n,m;
int va[N];
char s[N];
int suml[N],sumr[N];
int vis[N];
bool check(int mid)
{
for(int i=1;i<=n;i++) vis[i] = 0;
for(int i=1;i<=n;i++)
{
if(s[i]=='0')
{
int minn = min(i-suml[i],sumr[i]-i)+1;
if(minn<=mid) continue;
if(minn==mid+1) //最多能处理这些
{
if(suml[i]>=1&&!vis[suml[i]]) //尽量用左边的1，右边的留给别人，这样最贪心
{
vis[suml[i]] = 1;
continue;
}
if(sumr[i]<=n&&!vis[sumr[i]])
{
vis[sumr[i]] = 1;
continue;
}
}
return false;
}
}
return true;
}
signed main()
{
IOS;
cin>>T;
while(T--)
{
cin>>n;
cin>>s+1;
int maxnl = -inf,maxnr = inf;
for(int i=1;i<=n;i++)
{
if(s[i]=='0') suml[i] = maxnl;
else maxnl = i;
}
for(int i=n;i>=1;i--)
{
if(s[i]=='0') sumr[i] = maxnr;
else maxnr = i;
}
int l = 0,r = n;
while(l<r)
{
int mid = (l+r)>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
cout<<l<<"n";
}
return 0;
}

总结：
多多思考，别陷入某个思想里面了。

最后

以上就是合适台灯为你收集整理的2021桂林-Occupy the Cities-(思维+二分答案)的全部内容，希望文章能够帮你解决2021桂林-Occupy the Cities-(思维+二分答案)所遇到的程序开发问题。

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