解题思路
给定只含 ( 与 ) 的长度为偶数的字符串。一次操作可以任选两个下标交换字符（非相邻也可）。要求把整个序列变为平衡括号序列的最少交换次数。
核心结论（贪心）：从左到右扫描，用 bal 记录当前前缀中未匹配的左括号个数（看到 ( 则 bal++，看到 ) 则 bal--）。
- 当
bal 变为负数时，说明当前前缀中右括号比左括号多，无论最终目标是什么平衡序列，都至少需要一次交换，把某个后面的 ( 换到当前前缀里。
- 这一次交换可以把当前这段“过量右括号”的整段问题一起解决。在实现上，把这次交换的效果等价为把当前这个
) 当作 ( 处理：计数答案 ans++，并把 bal 设为 1（即从 -1 经过一次交换变成 +1）。
P3808.第3题-平衡的括号序列
题目内容
我们称一个括号序列为"平衡的括号序列"，当且仅当满足以下归纳定义：
1)空串是平衡的;
2)若字符串 A 是平衡的、则 “(A)” 是平衡的；
3)若字符串 A 与 B 均是平衡的，则 “AB” (连接)是平衡的。
例如：括号序列 ′()()′与 ′(())′ 是平衡的;而 ′)′、′)(′、′(′ 不是。
给定一个偶数长度的括号序列 s (仅包含 ′(′与 ′)′)。你可以进行若干次如下操作：
选择两个下标 i,j(1≤i<j≤n)，交换 si 与 sj 。
请你计算，最少需要进行多少次这样的交换，才能使整个序列变为一个平衡的括号序列。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦105) 表示数据组数。每组测试数据描述如下：
第一行输入一个偶数 n(2≦n≦2×105) ;
第二行输入一个长度为 n 的字符串 s (仅包含字符 ′(′ 与 ′)′)
保证所有测试中 n 的总和不超过 2×105 。保证对于每组测试，一定存在可行解。
输出描述
对于每组测试数据，输出一行一个整数，表示将 s 变为平衡括号序列所需的最少交换次数。
样例1
输入
4
2
)(
4
()()
4
))((
8
))))((((
输出
1
0
1
2
说明
样例一：交换位置 1 与 2 ，′)(′→′()′，最少 1 次。
样例二：s 已是平衡串，最少 0 次。
样例三：先交换位置 1 与 4 得到 ′()()′，最少 1 次。
