Balanced Sequence (贪心)

Balanced Sequence

题意

给你几个含有左右括号的串，你可以任意组合，求组合能得到的最大的括号匹配数量。

贪心。

具体贪心法可以见代码。

看！代码

#include <bits/stdc++.h>
#pragma comment(linker, “/STACK:1024000000,1024000000”)
using namespace std;
struct node{
    int left_no,right_no,yes;
    node()
    {
        left_no=right_no=yes=0;
    }
};
bool cmp(node a,node b)
{
    if(a.left_no>=a.right_no&&b.left_no<=b.right_no)//左少右多 + 左多右少 a前面
        return true;
    if(a.left_no<=a.right_no&&b.left_no>=b.right_no) //左少右多 + 左多右少 b前面
        return false;
    if(a.left_no<=a.right_no&&b.left_no<=b.right_no) //左少右多+左少右多 谁的左面数量多谁放前面
        return a.left_no>b.left_no;
    return a.right_no<b.right_no; // 左多右少 左多右少 谁的右边多谁放后面

}
char s[5000010];
int main()
{
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        vector<node>a(n);
        int len;
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            len=strlen(s);
            long long left=0,right=0,ans=0;
            for(int j=0;j<len;j++)
            {
                if(s[j]=='(')
                    left++;
                else
                {
                    if(left>0)  left--,ans++;
                    else    right++;
                }
            }
            a[i].left_no=left;
            a[i].right_no=right;
            a[i].yes=ans;
        }
        sort(a.begin(),a.end(),cmp);
        long long left=0,right=0,ans=0;
        for(int i=0;i<n;i++)
        {
            ans+=a[i].yes;
            if(left>=a[i].right_no)
                left-=a[i].right_no,ans+=a[i].right_no;
            else
                ans+=left,left=0;
            left+=a[i].left_no;
        }
        printf("%lld\n",ans*2);
    }
    return 0;
}