建议
做此题前先去看看这道题:P1739 表达式括号匹配
这道题是作为入门题出现的,主要的思路是用 栈 解决,为什么这么讲呢,emmmm~ STL也算是我们 C++ 党的一大优势对吧
思路
进入正题
我们其实可以将相邻的两个不同的数字给消去,舍去开头的 1 ,例如样例中给的 0111100101 我们按照规则对其进行处理,得到 01 111 00 10 1
可以发现,这里最后就剩下两个 0 了,可能有人会问:为什么最后的那个 1 不取呢? 这里解答一下,因为题目中未对子串进行要求,所以我们的子串可以取任意长度,只需使结果最大就可以了,如果这里把 1 取到了,就会使结果更小,所以这个 1 当然就会被舍去了。
对比
为什么说这道题很像 P1739 表达式括号匹配 呢,不知大家有没有发现,这里的 与 0 相邻的 1 可以看做是括号匹配中的 ‘ )’,把 0 看做是‘(’,那么就会发现,其实这道题就是在寻找不能匹配的括号数。
那么我们就可以用栈来进行 0 1 的配对消除
if(a[i]=='0') cxk.push(1);
if(a[i]=='1'&&(!cxk.empty())) cxk.pop();
maxx=max(maxx,k);
但是我们真的已经考虑到所有情况了吗?
想一想,会有两种特殊情况,一种是全是 1 的情况,另一种是全 0 的情况,那么我们会发现,我们需要对全 1 的情况进行特判;只需要在扫描的过程中加入对 1 的计数即可(当 1 的个数==size时,输出 -1
(全 1 的话 0 的个数为0,那么0-1=-1) )
鉴于这个难度,那么最后附上 AC (chou) 代码
代码
#include<bits/stdc++.h>
using namespace std;
string a;
int mn;
long long maxx;
signed main(){
ios::sync_with_stdio(false);
cin>>a;
stack<int>cxk;
for(int i=0;i<=a.size();i++)
{ if(a[i]=='1') mn++;
long long k=cxk.size();
if(a[i]=='0') cxk.push(1);
if(a[i]=='1'&&(!cxk.empty())) cxk.pop();
maxx=max(maxx,k);
}
if(mn==a.size()) cout<<"-1";
else cout<<maxx<<endl;
return 0;
}
最重要的一点就是任何题一定要考虑特殊情况 (貌似没特判全 1 情况的话是90分?)
码风及代码习惯不好,莫效仿