[HDOJ6299] 18多校01 Balanced Sequence (贪心)

发表于 | 更新于 | 分类于 ， ， | 评论数： | 阅读次数：

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

n个括号串，问如何排列这n个串，使得连起来后()匹配的对数最多（不用连续）。

首先串内匹配并记录答案。之后尽可能让左括号多的在左边，右括号多的在右边排序，再贪心扫一遍，只维护左括号的个数，同时根据下一个串右括号的个数统计答案。 

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
#include <bits/stdc++.h>
using namespace std;

using Node = struct {
  int l, r, v;
};
const int maxn = 100100;
int n;
vector<Node> p;
char s[maxn];

signed main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    p.resize(n);
    for(int i = 0; i < n; i++) {
      scanf("%s", s);
      int tot = 0;
      int l = 0, r = 0;
      for(int j = 0; s[j]; j++) {
        if(s[j] == '(') {
          l++;
        }
        else {
          if(l != 0) l--, tot++;
          else r++;
        }
      }
      p[i].l = l, p[i].r = r, p[i].v = tot;
    }
    sort(p.begin(), p.end(), [](Node a, Node b) {
      if(a.l > a.r) {
        return b.l > b.r ? a.r < b.r : true;
      }
      return b.l <= b.r ? a.l > b.l : false;
    });
    int l = 0, r = 0, ret = 0;
    for(int i = 0; i < n - 1; i++) {
      ret += p[i].v;
      l += p[i].l; r += p[i+1].r;
      ret += min(l, r);
      l -= min(l, r); r = 0;
    }
    ret += p[n-1].v;
    printf("%d\n", ret * 2);
  }
  return 0;
}