hdu 6299 Balanced Sequence（贪心）题解

题意：题意一开始不是很明白...就是他给你n个串，让你重新排列组合这n个串（每个串内部顺序不变），使得匹配的括号长度最大。注意，题目要求not necessary continuous，括号匹配不需要连续。

思路：我们先把每个串里面能组合的全部抵消，比如)((()抵消完为)((。我们能知道，这样操作完只会有4种情况留下：)))))，((((((((，)((((((，))))))))(。然后排序，排序的时候为了后面匹配能最大化利用所有括号，我们需要把左括号尽可能多的放在左边，右括号尽可能多的放在右边。

我觉得还是这样理解排序吧：我们需要匹配最大的匹配串，那么我们要尽可能创造出()，最好全是(((((((((和))))))))这种直接放左右两端，但是事实上我们还有)(((((和))))))((这两种，这两种怎么排呢？我们可以这样想：对于左括号比右括号多的，我们把他们放在左边更赚，这样左括号能更多的和下面的右括号匹配。但是如果两个都是左括号比右括号多呢？那就看谁的右括号更少，少的放前面，这样浪费右括号的可能性更少。另一种同理。

代码：

#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
const int maxn = 100000+5;
const int maxm = 100000+5;
const int MOD = 1e7;
const int INF = 0x3f3f3f3f;
using namespace std;
struct node{
    int l,r;
}p[maxn];
bool cmp(node a,node b){
    if(a.l > a.r) return b.l > b.r? a.r < b.r : true;
    if(a.l <= a.r) return b.l <= b.r? a.l > b.l :  false;
}
char s[maxn];
int main(){
    int n;
    int T;
    scanf("%d",&T);
    while(T--){
       scanf("%d",&n);
       int ans = 0;
       for(int i = 1;i <= n;i++){
            scanf("%s",s);
            int len = strlen(s);
            p[i].l = p[i].r = 0;
            for(int j = 0;j < len;j++){
                if(s[j] == '(') p[i].l++;
                else{
                    if(p[i].l > 0){
                        p[i].l--;
                        ans += 1;
                    }
                    else{
                        p[i].r++;
                    }
                }
            }
       }
       int unused = 0;
       sort(p + 1,p + n + 1,cmp);
       for(int i = 1;i <= n;i++){
            if(p[i].r > unused) p[i].r = unused;
            ans += p[i].r;
            unused -= p[i].r;
            unused += p[i].l;
       }
       printf("%d
",ans*2);
    }
    return 0;
}
/*
2
1
)()(()(
2
)
)(
*/