2021-02-07-2月7日题解

题解

该题为括号匹配问题，求最多能够匹配的对数，可以发现 )(，这种情况的括号一定不能够参与匹配，只有去除匹配括号后剩余全部为左括号或右括号才能够参与匹配，与其他的组成完整的括号序列。

代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
char a[500500]={0};
int num[500500]={0};
int b[100500]={0};
stack<char>s;
int main()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a+1);
        for(int j=1;a[j];j++)
        {
            if(s.empty())
            {
                s.push(a[j]);
            }
            else    
            {
                if(a[j]==')'&&s.top()=='(')
                    s.pop();
                else
                    s.push(a[j]);
            }
        }
        int sum1=0,flag=1;
        while(!s.empty())
        {
            if(s.top()==')')
            {
                s.pop();
                if(sum1>0)
                    flag=0;
                else
                    sum1--;
            }
            else
            {
                s.pop();
                if(sum1<0)
                    flag=0;
                else
                    sum1++;
            }
        }
        if(flag)
        {
            if(sum1<0)
                num[-sum1]++;
            b[i]=sum1;
            if(sum1==0)
                ans++;
        }
    }
    ans/=2;
    for(int i=1;i<=n;i++)
    {
        if(b[i]<=0)
            continue;
        else
        {
            if(num[b[i]]!=0)
                num[b[i]]--,ans++;
        }
    }
    cout<<ans<<endl;
}