2337. 奶牛贝茜的“笨蹄子”打字机
1000ms
256MB
简单
栈
题目描述
奶牛贝茜正在练习输入平衡括号字符串。由于操作失误，她输入的序列往往是不平衡的。
请帮助她计算，最少需要反转多少个字符（将 `(` 改为 `)`，或反之），才能使字符串变为平衡序列。
**平衡序列定义**：
1. 字符串包含的 `(` 和 `)` 数量相同。
2. 对于字符串的任意前缀，`(` 的数量不少于 `)` 的数量。
输入格式
一行，包含一个偶数长度的括号字符串。
- 字符串长度 $L \le 10^5$ 且 $L$ 为偶数。
输出格式
一个整数，表示最少需要反转的字符数。
样例 1
输入 (Input)
())(
输出 (Output)
2
样例说明
- **样例解释**：
对于 `())(`，我们需要将第三个 `)` 反转为 `(`，将第四个 `(` 反转为 `)`，变为 `(())`。总计反转 2 个。
- **算法提示**：
我们可以利用栈的思想来处理：
1. 遍历字符串，如果是 `(`，入栈；如果是 `)`，且栈不为空，则弹出一个 `(` 进行匹配。
2. 如果遇到 `)` 且栈为空，说明这个右括号是多余的，必须处理。
3. 遍历结束后，栈中剩下的左括号也是多余的。
4. 设扫描过程中“多余的右括号”数量为 $R_{extra}$，扫描结束后“剩余的左括号”数量为 $L_{extra}$。
5. 最小反转次数为：$\lceil R_{extra} / 2 \rceil + \lceil L_{extra} / 2 \rceil$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功