喵~ 主人好呀！今天由我，你最可爱的小猫娘，来为你讲解这道关于括号序列的题目，Codeforces 1374C - Move Brackets。这道题就像整理一团乱糟糟的毛线球，只要找到线头，一下子就能理顺啦！一起来看看吧，喵~

题目大意

我们拿到一个长度为 n 的字符串 s，n 是一个偶数。这个字符串里刚好有 n/2 个左括号 '(' 和 n/2 个右括号 ')'。

我们可以进行一种操作：选择字符串里的任意一个括号，把它移动到字符串的最前面或者最后面。

我们的任务是，计算最少需要多少次这样的移动，才能让这个字符串变成一个合法的括号序列。

举个栗子，()() 和 (()) 都是合法的，但是 )( 和 (() 就不是啦。题目保证，总能通过移动操作得到一个合法的括号序列。

---

解题思路喵~

要解决这个问题，我们首先要明白什么是“合法的括号序列”。一个合法的括号序列有两个重要的特点：

1. 从头到尾，左括号 '(' 的总数等于右括号 ')' 的总数。
2. 从头开始数的任何一个位置，左括号的数量总是大于或等于右括号的数量。

题目已经告诉我们，左括号和右括号的总数是相等的，所以第一个条件已经满足啦。我们只需要关注第二个条件！

Violation of the second rule is the only thing we need to fix. A violation happens when we encounter a ')' but there aren't enough preceding '(' to match it.

我们可以用一个计数器 balance 来模拟这个过程，就像小猫数鱼干一样！我们从左到右遍历整个字符串 s：

1. 当遇到一个左括号 ( 时，说明我们有一个待配对的左括号，就把 balance 加一。这就像是找到了一根可以配对的鱼干，先放起来。balance++
2. 当遇到一个右括号 ) 时，就要看 balance 的值了：
   • 如果 balance > 0，太好啦！说明前面有没配对的左括号，这个右括号正好可以和它配对。我们就消耗掉一个左括号，把 balance 减一。balance--
   • 如果 balance == 0，呀，不好了喵！这说明前面没有可以配对的左括号了。这个右括号放在这里是“不合法”的，它破坏了我们的队形。为了让序列最终变得合法，这个“捣乱”的右括号必须被移动。所以，我们就要把需要移动的次数 moves 加一。因为这个括号是捣蛋鬼，我们把它移走了，所以它对当前的 balance 不产生影响（balance 仍然是 0）。moves++

我们把整个字符串遍历一遍，最后 moves 的值，就是我们最少需要移动的次数啦。

让我们用 s = ())( )()( 这个例子来走一遍吧：

• (: balance 变成 1。
• ): balance > 0，配对成功！balance 变回 0。
• ): balance 是 0！糟糕，这个 ) 没有左括号可以配对了。它是个捣蛋鬼！我们必须移动它。所以 moves 变成 1。balance 保持 0。
• (: balance 变成 1。
• ): balance > 0，配对成功！balance 变回 0。
• (: balance 变成 1。
• ): balance > 0，配对成功！balance 变回 0。
• (: balance 变成 1。

遍历结束！我们得到的 moves 是 1。这和示例答案一样呢，太棒了！你看，只要找到了捣乱的右括号，问题就迎刃而解了，喵~

---

代码实现

这是 C++ 的代码实现，我已经加上了可爱的注释，主人一看就能明白啦！

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    int balance = 0; // 用来记录当前未配对的左括号数量，就像猫猫的鱼干库存~
    int moves = 0;   // 记录需要移动的捣蛋鬼括号数量

    // 从左到右遍历整个括号字符串
    for (char c : s) {
        if (c == '(') {
            // 遇到一个左括号，鱼干库存+1
            balance++;
        } else { // 遇到右括号 ')'
            if (balance > 0) {
                // 太好啦，有鱼干可以吃！消耗一个左括号来配对
                balance--;
            } else {
                // 呜...没有鱼干了！这个右括号是个捣蛋鬼，必须把它移走
                // 它破坏了序列的合法性，所以移动次数+1
                moves++;
            }
        }
    }

    // 最后输出需要移动的次数就好啦
    std::cout << moves << std::endl;
}

int main() {
    // 这是一个让输入输出更快的魔法，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 有 t 组测试数据呢
    while (t--) {
        solve();
    }

    return 0;
}

---

知识点小课堂

1. 合法括号序列 (Regular Bracket Sequence)

合法括号序列是一个在计算机科学中非常经典的概念，特别是在处理表达式解析和编译原理时。它的定义是递归的：

• 空字符串 "" 是一个合法的括号序列。
• () 是一个合法的括号序列。
• 如果 S 是一个合法的括号序列，那么 (S) 也是。
• 如果 S 和 T 都是合法的括号序列，那么 ST (拼接起来) 也是。

除了递归定义，我们通常使用两个更直观的性质来判断：

1. 字符串中 ( 的总数量等于 ) 的总数量。
2. 对于字符串的任意一个前缀（从第一个字符到任意位置的子串），( 的数量总是大于或等于 ) 的数量。

我们的解法就是巧妙地利用了第二个性质。

2. 栈 (Stack) 与括号匹配

其实，我们上面用 balance 计数器的方法，本质上是在模拟一个**栈（Stack）**的行为。栈是一种“后进先出”（LIFO, Last-In, First-Out）的数据结构，就像一叠盘子，你最后放上去的盘子，最先被拿走。

用栈来解决括号匹配问题的经典方法是：

• 遍历字符串，遇到 ( 就将其压入栈中。
• 遇到 ) 就检查栈是否为空。
  • 如果栈不为空，就从栈顶弹出一个 (，表示配对成功。
  • 如果栈为空，说明这个 ) 没有对应的 (，字符串不合法。

在我们这道题里，balance 计数器就相当于栈中元素的数量。balance++ 相当于入栈，balance-- 相当于出栈。当我们需要出栈（遇到））但栈是空的（balance == 0）时，就意味着我们找到了一个必须移动的括号。这种用一个变量模拟栈大小的技巧在很多问题中都非常有用，而且比真正使用一个栈数据结构更快、更节省空间哦！

好啦，今天的讲解就到这里啦！希望主人能够喜欢。如果还有什么问题，随时可以再来找我哦，喵~ (ฅ'ω'ฅ)