A5334. 移动括号
编程题
普及/提高-
知识点
题目描述
给你一个只由左括号
一次操作你可以：
- 选取字符串里的**一个**括号，把它挪到**最前面**或者**最后面**。
问：把 $s$ 变成**合法括号序列**，至少需要多少次操作？
> 合法括号序列的定义：
> -
> - 如果 $x$ 是合法，那么
> - 如果 $x,y$ 都合法，那么
> 例如：
你需要回答 $t$ 组独立测试。
( 和右括号 ) 组成的字符串 $s$，长度为 $n$，并且 $n$ 是偶数；同时 $s$ 里有一半是左括号、另一半是右括号。一次操作你可以：
- 选取字符串里的**一个**括号，把它挪到**最前面**或者**最后面**。
问：把 $s$ 变成**合法括号序列**，至少需要多少次操作？
> 合法括号序列的定义：
> -
"()" 是合法；> - 如果 $x$ 是合法，那么
"(" + x + ")" 也是合法；> - 如果 $x,y$ 都合法，那么
x + y 也合法。 > 例如：
"()()"、"(())"、"(())()" 都合法；而 ")("、"()(" 不合法。你需要回答 $t$ 组独立测试。
输入格式
- 第一行：一个整数 $t$，表示测试组数。
- 每组测试包含两行：
- 第一行：一个偶数 $n$（$2 \le n \le 50$）；
- 第二行：一个长度为 $n$ 的括号串 $s$，其中
- 每组测试包含两行：
- 第一行：一个偶数 $n$（$2 \le n \le 50$）；
- 第二行：一个长度为 $n$ 的括号串 $s$，其中
( 和 ) 的数量各为 $n/2$。输出格式
- 对每组测试，输出一行一个整数：把 $s$ 变成合法括号序列的最少操作次数。
输入输出样例
输入 #1
4 2 )( 4 ()() 8 ())()()( 10 )))((((())
输出 #1
1 0 1 3
说明/提示
## 数据范围
- $1 \le t \le 2000$
- $2 \le n \le 50$，$n$ 为偶数
- $s$ 中
### 样例解释
-
-
-
-
- $1 \le t \le 2000$
- $2 \le n \le 50$，$n$ 为偶数
- $s$ 中
( 和 ) 的数量相等### 样例解释
-
")("：把第一个 ) 移到串尾，得到 "()"，1 次。 -
"()()"：本来就是合法，0 次。 -
"())()()("：把最后一个 ( 挪到最前面即可，1 次。 -
")))((((())"：移动 3 次可变合法。