解题思路

给定只含 ( 与 ) 的长度为偶数的字符串。一次操作可以任选两个下标交换字符（非相邻也可）。要求把整个序列变为平衡括号序列的最少交换次数。

核心结论（贪心）：从左到右扫描，用 bal 记录当前前缀中未匹配的左括号个数（看到 ( 则 bal++，看到 ) 则 bal--）。

• 当 bal 变为负数时，说明当前前缀中右括号比左括号多，无论最终目标是什么平衡序列，都至少需要一次交换，把某个后面的 ( 换到当前前缀里。
• 这一次交换可以把当前这段“过量右括号”的整段问题一起解决。在实现上，把这次交换的效果等价为把当前这个 ) 当作 ( 处理：计数答案 ans++，并把 bal 设为 1（即从 -1 经过一次交换变成 +1）。

因此，答案就是扫描过程中 bal 首次降为负的次数（也可以理解为“需要从后面搬来左括号的段数”）。

相关算法：贪心 + 一次线性扫描。

实现方法：

1. 设 bal = 0, ans = 0；

2. 逐字符：

   • ( ⇒ bal++
   • ) ⇒ bal--
   • 若 bal < 0：ans++，bal = 1

3. 输出 ans 即为最少交换次数。 题目保证存在可行解（左右括号个数相等），上述算法成立。

复杂度分析

• 时间复杂度：对每个测试用例一次线性扫描，O(n)；全部用例总体 O(Σn)。
• 空间复杂度：仅常数额外变量，O(1)。

代码实现

Python

# 题意：任意两位置交换一次计为1次，求使括号串变为平衡串的最少交换次数
# 思路：线性扫描，bal<0 时需要一次交换，计数并将 bal 置为 1

import sys

def min_swaps_to_balance(s: str) -> int:
    bal = 0   # 未匹配的左括号数量
    ans = 0   # 需要的交换次数
    for ch in s:
        if ch == '(':
            bal += 1
        else:
            bal -= 1
        if bal < 0:
            # 需要从后面搬来一个 '(' 与当前过量的 ')' 交换
            ans += 1
            bal = 1  # 等价于把当前字符视为 '(' 之后的余额
    return ans

def main():
    data = sys.stdin.read().strip().splitlines()
    t = int(data[0].strip())
    idx = 1
    out_lines = []
    for _ in range(t):
        # 读取 n 与 s（n 实际不必使用）
        n = int(data[idx].strip()); idx += 1
        s = data[idx].strip(); idx += 1
        out_lines.append(str(min_swaps_to_balance(s)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 题意：任意下标交换一次计 1，求使括号串平衡的最少交换次数
// 思路：从左到右累加 bal；当 bal<0 时，需一次交换，答案+1，并将 bal 置为 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    // 外部函数：计算最少交换次数
    static int minSwapsToBalance(String s) {
        int bal = 0; // 未匹配的左括号数
        int ans = 0; // 交换次数
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') bal++;
            else bal--;
            if (bal < 0) {
                // 需要从后面搬一个 '(' 过来交换
                ans++;
                bal = 1; // 等价效果：把该位置当作 '(' 处理
            }
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        // 输入输出在主函数中（ACM 风格）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            // 读取 n 与 s（n 不参与计算，仅用于读取）
            int n = Integer.parseInt(br.readLine().trim());
            String s = br.readLine().trim();
            sb.append(minSwapsToBalance(s));
            if (tc + 1 < T) sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 题意：可任选两个位置交换一次，求把括号串变为平衡串的最少交换次数
// 思路：线性扫描，维护余额 bal；当 bal<0 说明当前前缀右括号过多，
// 必须进行一次交换，把后面的 '(' 换到前缀里；答案 +1，并将 bal 置为 1。

#include <bits/stdc++.h>
using namespace std;

int minSwapsToBalance(const string &s) {
    int bal = 0; // 未匹配的左括号计数
    int ans = 0; // 需要的交换次数
    for (char c : s) {
        if (c == '(') bal++;
        else bal--;
        if (bal < 0) {
            // 进行一次交换修复当前“过量右括号”的段
            ans++;
            bal = 1; // 交换后等价为把当前当作 '('
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    for (int tc = 0; tc < T; ++tc) {
        int n; string s;
        cin >> n >> s; // n 实际不使用
        cout << minSwapsToBalance(s) << (tc + 1 < T ? '\n' : '\0');
    }
    return 0;
}

题目内容

我们称一个括号序列为"平衡的括号序列"，当且仅当满足以下归纳定义：

1)空串是平衡的;

2)若字符串 $A$ 是平衡的、则 $“(A)”$ 是平衡的；

3)若字符串 $A$ 与 $B$ 均是平衡的，则 $“AB”$ (连接)是平衡的。

例如：括号序列 $'()()'$与 $'(())'$ 是平衡的;而 $')'、')('、'('$ 不是。

给定一个偶数长度的括号序列 $s$ (仅包含 $'('$与 $')'$)。你可以进行若干次如下操作：

选择两个下标 $i,j(1≤i<j≤n)$，交换 $s_i$ 与 $s_j$ 。

请你计算，最少需要进行多少次这样的交换，才能使整个序列变为一个平衡的括号序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦ 10^5)$ 表示数据组数。每组测试数据描述如下：

第一行输入一个偶数 $n(2≦n≦2×10^5)$ ;

第二行输入一个长度为 $n$ 的字符串 $s$ (仅包含字符 $'('$ 与 $')'$)

保证所有测试中 $n$ 的总和不超过 $2×10^5$ 。保证对于每组测试，一定存在可行解。

输出描述

对于每组测试数据，输出一行一个整数，表示将 $s$ 变为平衡括号序列所需的最少交换次数。

样例1

输入

4
2
)(
4
()()
4
))((
8
))))((((

输出

1
0
1
2

说明

样例一：交换位置 $1$ 与 $2$ ，$')('→'()'$，最少 $1$ 次。

样例二：$s$ 已是平衡串，最少 $0$ 次。

样例三：先交换位置 $1$ 与 $4$ 得到 $'()()'$，最少 $1$ 次。