2021桂林

桂林"/>

2021桂林

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;
}

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