解法类型：贪心排序，对称性。
一个括号序列 $S$ 对应着一个二元组 $(x,y)$，表示 $S$ 中有 $x$ 个未配对的右括号“)”，有 $y$ 个未配对的左括号“(”。例如，((( 对应二元组 $(0,3)$，)( 对应二元组 $(1,1)$，()) 对应二元组 $(1,0)$。
以下我们转而考虑括号序列对应的二元组。
能构成平衡的二元组序列的必要条件是 $sum_{i=1}^{n} x_i = sum_{i=1}^{n} y_i$。
$n$ 个二元组的某个排列 $p_1, p_2, dots, p_n$ 是平衡的当且仅当
对于 $i = 1, 2, dots, n$ 有
egin{equation}
x_{p_i} le sum_{j=1}^{i-1} y_{p_j} - x_{p_j} label{condition} ag{$igstar$}
end{equation}
将 $n$ 个二元组划分成两部分 $B_1$, $B_2$，第一部分满足 $x le y$，第二部分满足 $x > y$。
若有解，则一定存在一个解使得 $B_1$ 在 $B_2$ 之前。
事实上，若有解则按下述方法构造出的二元组序列一定是平衡的：
将 $B_1$ 中的二元组按 $x$ 从小到大排序，将 $B_2$ 中的二元组按 $y$ 从大到小排序。
可以通过对称性来解释这个算法的正确性：
我们把上面提到的分组方法改一下：将 $n$ 个二元组分成三组 $B_1 := {(x,y): x < y}$，$B_2 := {(x,y): x > y}$，$B_3 := {(x,y) : x = y} $。
依据直觉我们可以按下述方法排列给定的 $n$ 个二元组
- 按 $B_1,B_3, B_2$ 的顺序排列。
- 将 $B_1$ 里的二元组按 $x$ 从小到大排列，检查如此排列是否满足条件 eqref{condition}，若不满足则无解。
- 若 $max{x : (x,x)in B_3} > sum_{(x,y)in B_1}y - x$，则无解，否则将 $B_3$ 里的二元组以任意顺序排列。
- 考虑如何排列 $B_2$？
考虑把给定的 $n$ 个括号序列反转，也就是先把左括号变成右括号再把头尾反转。例如()(( 变成 ))()，这样对应的二元组由 $(x,y)$ 变为 $(y,x)$。显然变换之前有解当且仅当变换之后有解。变换之后，$B_3$ 不变，$B_1, B_2$ 恰好“角色互换”：将变换之后的 $B_1, B_2$ 记作 $B'_1, B'_2$，把 $B'_1$ 里的二元组的 $x,y$ 互换即得到 $B_2$，把 $B'_2$ 里的二元组的 $x,y$ 互换即得到 $B_1$。
不难看出，给定的 $n$ 个括号序列能排列成平衡的括号序列当且仅当 $B_1, B'_1$ 都满足上述第 2 个条件且 $B_3$ 满足上述第 3 个条件。
void solve() {
auto check = [](vector<pair<int,int>>& p) {
sort(p.begin(), p.end(), [](auto& a, auto& b){return a.first < b.first;});
int n_left = 0;
for (auto x : p) {
if (x.first > n_left) return -1;
n_left += x.second - x.first;
}
return n_left;
};
int n;
cin >> n;
vector<pair<int,int>> B1, B2;
int mx = 0;
int need = 0, give = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
int need_l = 0, give_l = 0;
for (auto x : s) {
if (x == '(') ++give_l;
else {
if (give_l > 0) --give_l;
else ++need_l;
}
}
need += need_l;
give += give_l;
if (need_l == give_l) mx = max(need_l, mx);
else if (need_l < give_l) B1.emplace_back(need_l, give_l);
else B2.emplace_back(give_l, need_l);
}
cout << (need == give and mx <= check(B1) and check(B2) >= 0 ? "Yes" : "No") << '
';
}