题目描述
链接: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); } }