← 返回题目列表

Codeforces · 2206/M

M. 平衡变形

中文机器翻译题面 查看原题

在此问题中,两个字符串 $$$T$$$ 和 $$$U$$$ 的串联由 $$$T+U$$$ 表示。

仅由括号组成的字符串(左括号 '(' 或右括号 ')') 是 平衡 当且仅当它是以下之一。

  • 空字符串。
  • 两个非空平衡字符串的串联。
  • 连接 $$$\texttt{(} + T + \texttt{)}$$$,其中 $$$T$$$ 是平衡字符串。
例如,“()“和”(())()“是平衡的,而”()(“和”((()“不是。

字符串是 变形 当且仅当它是以下之一。

  • 字符串“)".
  • 连接 $$$T + \texttt{)} + U$$$,其中 $$$T$$$ 和 $$$U$$$ 是变形字符串。
  • 连接 $$$\texttt{(} + T + \texttt{(}$$$,其中 $$$T$$$ 是变形字符串。
例如,“()(“和”))()(“变形了,而”()“和”(()“不是。

字符串 $$$T$$$ 平衡变形 如果 $$$T$$$ 变形并且串联 $$$T + \texttt{)}$$$ 平衡。例如,字符串“()(“平衡变形。

给定一个字符串 $$$S$$$,长度为 $$$n$$$,仅由括号组成。在给定的输入约束下,可以证明存在字符串 $$$X$$$ 和 $$$Y$$$,使得串联 $$$X + S + Y$$$ 具有变形平衡。确定 $$$|X| 的最小可能值+ |Y|$$$($$$X$$$ 和 $$$Y$$$ 的长度之和)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) 表示测试用例的数量。之后,$$$t$$$ 测试用例如下。它们各自介绍如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。

第二行包含长度为 $$$n$$$ 的字符串 $$$S$$$,仅包含 '(' 或 ')'.

一个输入文件中所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出 $$$|X|+|Y|$$$ 的最小可能值,使得串联 $$$X + S + Y$$$ 具有变形平衡。

示例

输入
复制

3
3
()(
1
)
7
(())())

输出
复制

0
2
4

注意

示例输入/输出#1 的说明

对于第一个测试用例,给定的弦已经具有变形的平衡。

对于第二个测试用例,将 $$$X$$$ 和 $$$Y$$$ 设置为“(“产生串联”()(”,其平衡变形。$$$|X|+|Y|$$$ 的值为 $$$2$$$。

对于第三个测试用例,只需将 $$$X$$$ 设置为“((()" 和 $$$Y$$$ 为空字符串以获得 $$$|X|+|Y|$$$ 的最小值。