HDU 6299 Balanced Sequence(贪心)

题目：给出N个只有左右括号字符串，这N个字符串的排列顺序是任意的，问按最优的排序后，得到最多匹配的括号个数

分析：我们很容易的想到字符串)()()(( , 这样的字符串可以精简为)(( 因为无论如何的排序，对于字符串可以匹配的括号是不会变的；

那么问题就可以简化为对与 **)(** ）（这几种类型的字符串的排序情况；

我们也很自然而然的想到了贪心，那问题来了，我们该如何贪心呢？先从小问题出发，有A 与 B两串，在自然的可以想到排序的情况肯定是AB或者BA 看谁的匹配度高吧，那依据这样的思想，定义出完整的贪心规则：

1.A.sumz<=A.sumy && B.sumz>b.sumy 就是说明AB这样可以更加优秀

2.A.sumz>A.sumy && B.sumz<=B.sumy 就是说明BA这样的更优秀的

3.如果 1 / 2 两种情况都不是那就是说匹配度一样，那很自然的可以想到右括号多的在后面，左括号多的在前面

好了AC了，太遗憾这题。。贪心的规则打错了，但思路是没问题的，还需加油呀

#include<bits/stdc++.h>

using namespace std ;

char str[],sta[];

struct no

{

    int sumz , sumy;

}a[];

bool cmp(no a , no b)

{

    if(a.sumz<=a.sumy && b.sumz>b.sumy)

    return ;

    if(a.sumz>a.sumy && b.sumz<=b.sumy)

    return ;

    if(a.sumy>=a.sumz && b.sumy>=b.sumz)

    return a.sumz<b.sumz;

    return a.sumy>b.sumy;

}

int main()

{

    int t,n,top,sum,sumz,sumy;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

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

        {

            a[i].sumz=a[i].sumy=;

        }

        sum=;

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

        {

            scanf("%s",str);

            int Len=strlen(str);

            top=sumz=sumy=;

            for(int j= ; j<Len ; j++)

            {

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

                {

                    a[i].sumy++;

                }

                else

                {

                    if(a[i].sumy)

                    {

                        a[i].sumy--;sum++;

                    }

                    else

                    {

                        a[i].sumz++;

                    }

                }

            }

        }

        sort(a,a+n,cmp);

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

        {

            if(a[i].sumz<a[i-].sumy)

            {

                sum+=a[i].sumz;

                a[i].sumy=a[i].sumy+(a[i-].sumy-a[i].sumz);

            }

            else if(a[i].sumz==a[i-].sumy)

            sum+=a[i].sumz;

            else

            {

                sum+=a[i-].sumy;

                a[i].sumz=a[i].sumz-a[i-].sumy;

            }

        }

       printf("%d\n",*sum);

    }

}

巴特西

HDU 6299 Balanced Sequence(贪心)

最新文章

热门文章