HDU6299（2018多校第一场）

Bryce1010模板

 http://acm.hdu.edu.cn/showproblem.php?pid=6299

两个字符串的排序可以分成四种情况：

（1）str1左少右多 vs str2 左多右少

str2排在str1前面

（2）str1 左多右少 vs str2 左少右多

str1排在str2前面

（3）str1 左少右多 vs str2 左少右多

按左括号的数量排序

（4）其他情况按右括号的数量排

 if(l<=r&&s.l>s.r)//左少右多  vs  左多右少

        {

            return false;

        }

        if(l>r&&s.l<=s.r)//左多右少  vs  左少右多

        {

            return true;

        }

        if(r>=l&&s.r>=s.l)//左少右多  vs  左少右多

        {

            return l>s.l;

        }

        return r<s.r;

最后用一个if维护左括号的数量，不断更新对应右括号的最大值（从dls的代码学到的）

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXN=1e5+10;

struct Str

{

    int l,r,add;

    bool operator < (const Str& s)const

    {

        if(l<=r&&s.l>s.r)//左少右多  vs  左多右少

        {

            return false;

        }

        if(l>r&&s.l<=s.r)//左多右少  vs  左少右多

        {

            return true;

        }

        if(r>=l&&s.r>=s.l)//左少右多  vs  左少右多

        {

            return l>s.l;

        }

        return r<s.r;

    }

}str[MAXN];

char s[MAXN];

int main()

{

    //freopen("in.txt","r",stdin);

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

         for(int i=1;i<=n;i++)

        {

            scanf("%s",s);

            str[i].l=str[i].r=str[i].add=0;

            int len=strlen(s);

            //count括号

            for(int j=0;j<len;j++)

            {

                if(s[j]=='(')

                    str[i].l++;

                else

                {

                    if(str[i].l>0)

                        str[i].l--,str[i].add++;

                    else

                        str[i].r++;

                }

            }

        }

        sort(str+1,str+1+n);

        int ans=0;

        int now=0;

        for(int i=1;i<=n;i++)

        {

            if(str[i].r>now)

            {

                str[i].r=now;

            }

            ans+=str[i].r+str[i].add;

            now-=str[i].r;

            now+=str[i].l;

        }

        cout<<ans*2<<endl;

    }

}

巴特西

HDU6299（2018多校第一场）

最新文章

热门文章