题解

题目描述

给定一个长度为 $N$ 的只包含左括号 '(' 和右括号 ')' 的字符串，多多君每次可以顺序读取如下两种内容之一：

1. 一个单独的字符（'(' 或 ')'），算作 1 次处理。
2. 一个“有效括号子串”，算作 1 次处理。
   • 有效括号子串需满足：
     • 括号成对闭合；
     • 正确嵌套。

求将整个字符串处理完所需的最小处理次数。

思路

为了最小化处理次数，我们希望每次尽可能地“多读”——即在当前位置 $i$ 能读到的最长的有效括号子串，若无法读到任何有效子串，则退而读一个单字符。

1. 初始化操作次数 ans = 0，当前指针 i = 0。
2. 当 $i < N$ 时：
   1. 若 s[i] == ')'，则显然不能作为有效子串起点，只能单读此字符：$$\text{ans} \mathrel{+}= 1,\quad i \mathrel{+}=1.$$
   2. 否则（s[i] == '('）：
      • 用两个变量维护：
        • $cnt$：当前扫描的括号平衡度；
        • $last\_zero$：记录从 $i$ 开始扫描至今，$cnt$ 首次降为 $0$（表示一个有效子串末端）的最远位置。
      • 从 $j=i$ 扫描到 $j=N-1$：
        • 遇到 '(' 则 $cnt\!+\!1$，遇到 ')' 则 $cnt\!-\!1$；
        • 若 $cnt<0$，说明前缀已失衡，后续无法成为有效子串，立即中断；
        • 若 $cnt==0$，更新 $last\_zero=j$。
      • 扫描结束后若 $last\_zero \neq -1$，说明存在起始于 $i$ 的有效子串，且其最远末端为 $last\_zero$，我们取之：
        $ans+=1,i\leftarrow last\_zero+1.$
        否则，说明当前位置无法组成任何有效子串，只能单读：
        $\text{ans}\mathrel{+}=1,\quad i\mathrel{+}=1.$
3. 输出 ans 即为最小处理次数。

该贪心策略每步都尽可能多地“消费”有效子串，保证了全局最优。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string s;
    cin >> s;

    int ans = 0;      // 记录操作次数
    int i = 0;        // 当前处理指针
    while (i < N) {
        if (s[i] == ')') {
            // 不能成为有效子串起点，只能单读
            ans++;
            i++;
        } else {
            int cnt = 0;         // 括号平衡度
            int last_zero = -1;  // 记录 cnt 回到 0 时的最远位置
            // 尝试扫描最长有效子串
            for (int j = i; j < N; j++) {
                if (s[j] == '(') cnt++;
                else cnt--;
                if (cnt < 0) break;        // 失衡，无法继续
                if (cnt == 0) last_zero = j;
            }
            if (last_zero != -1) {
                // 找到有效子串[i..last_zero]
                ans++;
                i = last_zero + 1;
            } else {
                // 无有效子串，只能单读
                ans++;
                i++;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

Python

def min_operations(s: str) -> int:
    n = len(s)
    ans = 0    # 操作次数
    i = 0      # 当前指针
    while i < n:
        if s[i] == ')':
            # 无效子串起点，单读
            ans += 1
            i += 1
        else:
            cnt = 0
            last_zero = -1
            # 扫描最长有效括号子串
            for j in range(i, n):
                if s[j] == '(':
                    cnt += 1
                else:
                    cnt -= 1
                if cnt < 0:
                    break
                if cnt == 0:
                    last_zero = j
            if last_zero != -1:
                # 取最长有效子串
                ans += 1
                i = last_zero + 1
            else:
                # 单读
                ans += 1
                i += 1
    return ans

if __name__ == "__main__":
    N = int(input().strip())
    s = input().strip()
    print(min_operations(s))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        String s = in.next();
        int ans = 0;  // 操作次数
        int i = 0;    // 当前指针
        while (i < N) {
            if (s.charAt(i) == ')') {
                // 无效子串起点，单读
                ans++;
                i++;
            } else {
                int cnt = 0;
                int lastZero = -1;
                // 扫描最长有效子串
                for (int j = i; j < N; j++) {
                    if (s.charAt(j) == '(') cnt++;
                    else cnt--;
                    if (cnt < 0) break;        // 失衡
                    if (cnt == 0) lastZero = j;
                }
                if (lastZero != -1) {
                    // 取最长有效子串
                    ans++;
                    i = lastZero + 1;
                } else {
                    // 单读
                    ans++;
                    i++;
                }
            }
        }
        System.out.println(ans);
        in.close();
    }
}

题目内容

多多君在处理一个由左括号(和右括号)组成的字符串，多多君每次处理时可以顺序读取一个字符或者一个有效括号子串，求问多多君的最小处理次数

输入描述

第一行输入为一个整数 $N$ ,表示字符串的总长度 $(1<= N<=10,000)$

第二行输入为一个长度为 $N$ 字符串，字符串由 $($ 和 $)$ 组成

输出描述

输出为一个整数，表示字符串的最小处理次数

补充说明

有效括号子串需要满足：

1.括号成对闭合：每个 $'('$ 都有一个对应的 $')'$

2.正确嵌套顺序：右括号不能出现在对应的左括号之前

例如：$“()”、“()()”、“(()())”$ 均为有效括号子串，$“)(”、“(()”、“()())"$ 不是有效括号子串

样例1

输入

4
()()

输出

1

说明

$()()$ 为有效括号子串，需要处理一次

样例2

输入

6
((()()

输出

3