Balanced Sequence（毒瘤啊）排序贪心 HDU多校

Problem Description

Chiaki has

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output an integer denoting the answer.

Sample Input

2 1 )()(()( 2 ) )(

Sample Output

4 2

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1e5 + 10;
 5 struct node {
 6     int l, r, sum;
 7 } qu[maxn];
 8 int cmp(node a, node b) {
 9     if (a.r <  a.l && b.r >= b.l) return 1;
10     if (a.r >= a.l && b.r <  b.l) return 0;
11     if (a.r >= a.l && b.r >= b.l)  return a.l > b.l;
12     return a.r < b.r;
13 }
14 int n, t;
15 char s[50 * maxn];
16 int main() {
17     scanf("%d", &t);
18     while(t--) {
19         scanf("%d", &n);
20         for (int i = 0 ; i < n ; i++) {
21             scanf("%s", s);
22             qu[i].l = qu[i].r = qu[i].sum = 0;
23             int len = strlen(s);
24             for (int j = 0 ; j < len ; j++) {
25                 if (s[j] == '(') qu[i].l++;
26                 else {
27                     if (qu[i].l > 0) qu[i].l--, qu[i].sum++;
28                     else qu[i].r++;
29                 }
30             }
31         }
32         sort(qu, qu + n, cmp);
33         int ans = 0, cnt = 0;
34         for (int i = 0 ; i < n ; i++) {
35             if (qu[i].r > cnt) {
36                 ans += cnt + qu[i].sum;
37                 cnt = 0;
38             } else {
39                 ans += qu[i].r + qu[i].sum;
40                 cnt -= qu[i].r;
41             }
42             cnt += qu[i].l;
43         }
44         printf("%d
", ans * 2);
45     }
46     return 0;
47 }