2020题解

题目描述
链接：https://ac.nowcoder.com/acm/contest/7502/A

题目大意：寻找坐标不重叠的2020的对数
思路：可以发现“2020”，前后是一样的，所以我们可以通过栈来寻找20的对数(su)，但是存在一种不符合条件的情况例如：222000，这种情况当'20'的对数大于su/2对答案是没有贡献的，需要减去即可。
所以我们使用前缀和思想对匹配最近匹配的'2' '0'之间+1来记录一下
自己可以将a数组打表理解一下前缀和
AC代码

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        stack<int>st;
        char c;
        int su=0,ma=-1,an;//su记录匹配的20的对数
        memset(a,0,sizeof a);
        for(int i=1;i<=n;++i)
        {
            scanf(" %c",&c);
            if(c=='0'&&!st.empty())
                a[st.top()]++,st.pop(),a[i+1]--,++su;
            else if(c=='2')
                st.push(i);
        }
        for(int i=1;i<=n;++i)
            a[i]+=a[i-1],ma=max(ma,a[i]);//ma指不符合条件的20的对数，例如222000
        if(ma<=su/2)an=su/2;
        else an=su-ma;
        printf("%d\n",an);
    }
}