据说用了张森不等式，没怎么研究过，这里完全看了dls的代码QAQ
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn=5e5+1000; struct note { int l,r; int rs; bool operator <(const note &p) const//尽量使排序后前面'('多，后面')'多 { if(r>=l&&p.l>p.r) return 0; if(l>r&&p.r>=p.l) return 1; if(r>=l&&p.r>=p.l) return l>p.l; return p.r>r; } }aa[maxn]; int t; int n; char ss[maxn]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); getchar(); for(int i=1;i<=n;i++) { aa[i].l=aa[i].r=aa[i].rs=0; scanf("%s",ss); int nn=strlen(ss); for(int j=0;j<nn;j++) { if(ss[j]=='(') aa[i].l++; else { if(aa[i].l>0) { aa[i].l--; aa[i].rs++;//可以形成一组() } else aa[i].r++; } } } sort(aa+1,aa+1+n); int ans=0; int nowl=0;//由上一个aa继承的左括号数 for(int i=1;i<=n;i++) { if(aa[i].r>nowl) aa[i].r=nowl;//min(aa[i].r,nowl)就使能配对的数量 ans+=aa[i].r+aa[i].rs; nowl+=aa[i].l;//加上'('的数量 nowl-=aa[i].r;//减去已经配对的数量 } printf("%d\n",ans*2); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/9362754.html
