2018 Multi-University Training Contest 1 Balanced Sequence（贪心）

题意：

t组测试数据，每组数据有 n 个只由 '(' 和 ')' 构成的括号串。

要求把这 n 个串排序然后组成一个大的括号串，使得能够匹配的括号数最多。

如()()答案能够匹配的括号数是 4，(()) 也是 4。

例如：

n = 2

)

)((

你可以将其排序为))((，数目为0，也可以将其排序为)(()，数目为1。

解法：

贪心。

把所有字符串中本身能够匹配的括号全部去掉，然后剩下的字符串只有三种：

1、全是 '('

2、全是 ')'

3、一串 ')' 加一串 '('

对于每一种字符串，如果 '(' 的数目多于 ‘)’，就把它放在前面，按照字符串中的 ‘)’ 从小到大排序。

　　　　　　　　　如果 ')' 的数目多于 ‘(’，就把它放在后面，按照字符串中的 ‘(’ 从大到小排序。

然后统计新串合法的括号数即可。

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

#define maxn 100000 + 1000

struct Node

{

    int x, y;

}a[maxn];

bool cmp(Node a, Node b)

{

    if (a.x-a.y >=  && b.x-b.y < ) return true;

    if (a.x-a.y <  && b.x-b.y >= ) return false;　　　　// 左括号数目>右括号数目的，一定在右括号>左括号的前面

    if (a.x-a.y >=  && b.x-b.y >= ) return a.y < b.y;　　　　//都是左括号比有括号多，按照右括号的数量从小到大排序

    if (a.x-a.y <  && b.x-b.y < ) return a.x > b.x;　　　　　//都是左括号比右括号少，按照左括号的数量从大到小排序

}

int main()

{

    int t;

    scanf("%d", &t);

    for (int ca = ; ca <= t; ca++)

    {

        int n, ans = ;

        scanf("%d", &n);

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

        {

            char s[maxn];

            scanf("%s", s);

            a[i].x = a[i].y = ; //a[i].x 记录左括号的数量， a[i].y 记录右括号的数量。

            for (int j = ; s[j] != '\0'; j++)

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

                {

                    if (a[i].x) {a[i].x--; ans++;}

                        else a[i].y++;

                }

                else a[i].x++;
　　　　　　//括号匹配

        }

        sort(a+, a++n, cmp);

        int instack = ;

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

        {

            if (a[i].y && instack)

            {

                ans += min(a[i].y, instack);

                instack = max(, instack-a[i].y);

            }

            instack += a[i].x;

        }
　　　　//最后进行一次括号匹配，继续统计答案。

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

    }

}

巴特西

2018 Multi-University Training Contest 1 Balanced Sequence（贪心）

最新文章

热门文章