HDU-6299 Balanced Sequence(贪心)

传送门

思路：就是求连接后最多有几对括号能匹配。将预处理后的字符串分成3组，1.仅含'(‘ 2.先’)’后'(‘ 3.仅含’)’。

贪心时，讲第一种放在最前面，第三种放在最后面。

对第二种来说，分成两种：

‘(‘-‘)’贡献值为正的，’)’越少的放越前面

‘(‘-‘)’贡献值为负的，'(‘越多的放越前面

最后模拟一下即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

char s[100005];
struct node{
int l,r;
};
vector<node>v;
bool cmp3(node a,node b)///重点
{
    if ((a.l-a.r>0)&&(b.l-b.r<=0))
        return true;
    if ((b.l-b.r>0)&&(a.l-a.r<=0))
        return false;
    if ((a.l-a.r>0)&&(b.l-b.r>0))
        return a.r<b.r;
    if ((a.l-a.r<=0)&&(b.l-b.r<=0))
        return a.l>b.l;
}
int ls,rs;
int main()
{
    int ww;
    scanf("%d",&ww);
    while (ww--)
    {
        int n;
        int ans=0;
        ls=rs=0;
        scanf("%d",&n);
        v.clear();
        for (int i=0;i<n;i++)
        {
            scanf("%s",s);
            int l=0,r=0;
            int ll=strlen(s);
            for (int j=0;j<ll;j++)
            {
                if (s[j]==')')
                {
                    if (l==0)
                        r++;
                    else
                    {
                        l--;
                        ans++;
                    }
                }
                else
                    l++;
            }
            if (r==0)
                ls+=l;
            else if (l==0)
                rs+=r;
            else
            {
                v.push_back((node){l,r});
            }
        }
        sort(v.begin(),v.end(),cmp3);
        int ll=ls;
        for (int i=0;i<v.size();i++)
        {
            if (ll>=v[i].r)
            {
                ll-=v[i].r;
                ans+=v[i].r;
            }
            else
            {
                ans+=ll;
                ll=0;
            }
            ll+=v[i].l;
        }
        ans+=min(ll,rs);
        printf("%d\n",ans*2);
    }
    return 0;
}