[ 2018 Multi-University Training Contest 1 ] [ HDU6299 ] B Balanced Sequence

        题意：将n个由'('和')'组成的字符串任意串接在一起，求从中能够取出的最长的满足括号匹配的子序列的长度。\(1 \leq n \leq 10^5 , 1 \leq |s_i| \leq 10^5 , \sum{|s_i|} \leq 5 \cdot 10^6\)。

        题解：将每个串中最长的满足括号匹配的序列全部取出来，剩下的部分就是形如\(")))((("\)这样的形式的，即一些右括号与一些左括号组成。记每个串这样处理出来后右括号数为a（就是左半边的括号数），左括号数为b，每个串都能表示成\( (a,b) \)的形式，接下来就是要对这些串排序使结果最优。

        考场上的做法基本上就是取多种排序方式求结果然后取最大值了。标算的排序做法是这样的：把串按照\(a < b\)和\( a \geq b\)分成两类，先取\( a < b\)的，在\( a < b\)这类中a小的先取，在\(a \geq b\)这类中b大的先取，然后扫一遍求出答案。大致证明一下：

        考虑交换相邻位置的两个串。考虑位于i和i+1的两个串，其中\( a_i \geq b_i \)且\( a_{i+1} < b_{i+1} \)，交换两串不影响i之前的串，而在i+1之后的串，由于i+1之前左括号的总数在两串交换前后不会改变，且在i+1之后能够被使用的右括号也是固定且有限的，所以在交换i与i+1与不交换两种情况下的最优的策略一定是在i+1之前用掉最多的左括号的那个。设i之前剩下的左括号数为x，枚举所有情况，可以发现交换后更优（写起来不好写，式子大小不好比较，但是直接看很容易看出来，所以就懒得写了...）。同类情况考虑方法一样，比较容易，就不写了。

        然后根据大佬们的OI/ACM经验，这应该是全局最优的排序方法，于是按照这种方案排序做就好了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pair;
const int maxn=1e5+10;

char s[maxn];
Pair P[maxn];
int n,ans;

bool cmp(const Pair &a,const Pair &b)
{
	if ((a.first<a.second)>(b.first<b.second)) return true;
	if ((a.first<a.second)<(b.first<b.second)) return false;
	if (a.first<a.second) return a.first<b.first;
	else return a.second>b.second;
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		ans=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%s",s);
			int len=strlen(s);
			int cl=0,cr=0;
			for (int j=0;j<len;j++)
			if (s[j]=='(') cl++;
			else if (cl) ans+=2,cl--;
			else cr++;
			P[i].first=cr;
			P[i].second=cl;
		}
		sort(P+1,P+1+n,cmp);
		for (int i=1,cl=0;i<=n;i++)
		{
			int tmp=min(cl,P[i].first);
			ans+=tmp<<1;
			cl+=P[i].second-tmp;
		}
		printf("%d\n",ans);
	}
}