HDU 6299 Balanced Sequence 【贪心】

发表于 | 更新于 | 分类于

题目大意：

现有n个字符串，每个串均有若干个()左右括号构成，请你选择一个连接顺序将这些串连在一起，使得匹配的括号对数最多。
括号匹配的定义为左括号在右括号左边，每个括号均有一次参与匹配的机会。

解题思路：

首先在输入时对串进行处理，将已经匹配的记录下来，这样剩下的串只有4种情况：1.空串 2.只有左括号 3.只有右括号 4.右括号和左括号的混合 && 右括号一定在左括号前边。
首先第1种情况肯定不用管了，剩下的该如何安排他们的顺序使得配对的数目最大化呢？肯定是要左括号尽量往左靠，右括号尽量往右靠，这样第2、3种情况也解决了。
最后一种是情况最多的，可以分为 (1).右括号数 > 左括号数 (2).左括号数 > 右括号数 以及 (3).左括号数 == 右括号数。考虑我们最初的目的，左括号尽量往左是为了什么？是为了不“浪费”这些括号，但是当必须“牺牲”一部分括号时，应当将“浪费”降到最低。于是我们找出了排序的关键字key = 左括号数 - 右括号数。两个变量相比较共四种情况：1.key1 > 0 && key2 > 0 2.key1 > 0 && key2 < 0 3.key1 < 0 && key2 > 0 4.key1 < 0 && key2 < 0，再将相等的情况随便插到几组中所有情况就都有了。这时排序的规则是一正一负正的在前，都为正时右括号少的在前，都为负时左括号多的在前，根据这样排完序挨个取就可以了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5+5;

char s[MAX];
int t, n, tem, res;
struct node
{
    int l, r, sub;
}a[MAX];
bool cmp(node u, node v)
{
    if(u.sub >= 0 && v.sub < 0)
        return true;
    if(u.sub < 0 && v.sub >= 0)
        return false;
    if(u.sub >= 0 && v.sub >= 0)
        return u.r < v.r;
    return u.l > v.l;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        res = 0;
        memset(a, 0, sizeof(a));
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s);
            tem = 0;
            for(int j = 0; s[j]; ++j)
            {
                if(s[j] == '(')
                    ++tem;
                else
                {
                    if(tem == 0)
                        ++a[i].r;
                    else
                    {
                        --tem;
                        ++res;
                    }
                }
            }
            a[i].l = tem;
            a[i].sub = a[i].l - a[i].r;
        }
        sort(a, a + n, cmp);
        tem = a[0].l;
        for(int i = 1; i < n; ++i)
        {
            res += min(tem, a[i].r);
            tem -= a[i].r;
            if(tem < 0) tem = 0;
            tem += a[i].l;
        }
        printf("%d\n", res<<1);
    }
    return 0;
}
Donate comment here
0%