博客

题解

题目重点：

• 条件1：对于字符串的任意前缀，所包含的 ( 的数目都不少于 ) 的数目。

• 条件2：输入的字符串满足：最多只修改一个字符，即可变为平衡括号字符串。

因此本题限制在了只需要变化一个括号就一定能序列匹配！

结题思路：

• 分类：1.左右括号数R L相同；2.右括号需要转化为左括号：R=L+2；左括号需要转化为有括号：L=R+2

• 类型①：输出0直接

• 类型②：记录每个位置的从左到右 左右括号分别的前缀和，由条件1可得：从左向右搜索第一个左括号比右括号少的右括号位置， 则位置及其之前的任意一个右括号改变为左括号才能满足条件1，答案为此位置的右括号前缀和

• 类型③：记录每个位置的从右到左 左右括号分别的前缀和，由条件1可得：从右向左搜索第一个右括号比左括号少的左括号位置，则该位置及其右侧任意一个左括号改变为右括号就可以满足条件1，答案为此位置的左括号前缀和

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
        string arr;
        cin>>arr;
        int n = arr.length();
        int L = 0,R = 0;
        for(int i = 0;i<n;i++){
                if(arr[i] == '(') L++;
                else R++;
        }
        int sumL[n+1] = {0}; // 前缀和
        int sumR[n+1] = {0};
        if(L == R){
                cout<<0<<endl;
        }else if(L < R){
                // 右括号需要转化为左括号：R=L+2
                for(int i = 0;i<n;i++){
                        sumL[i+1] = sumL[i];
                        sumR[i+1] = sumR[i];
                        if(arr[i] == '(') sumL[i+1] = sumL[i+1] + 1;
                        else sumR[i+1] = sumR[i+1] + 1;
                        // 判断 第一个左括号比右括号少的右括号位置
                        if(arr[i] == ')' and sumL[i+1] < sumR[i+1]){
                                cout<<sumR[i+1]<<endl;
                                break;
                        }
                }
        }else{
                // 左括号需要转化为有括号：L=R+2
                for(int i = n-1;i>=0;i--){
                        sumL[i] = sumL[i+1];
                        sumR[i] = sumR[i+1];
                        if(arr[i] == '(') sumL[i] = sumL[i] + 1;
                        else sumR[i] = sumR[i] + 1;
                        // 判断 第一个右括号比左括号少的左括号位置
                        if(arr[i] == '(' and sumL[i] > sumR[i]){
                                cout<<sumL[i]<<endl;
                                break;
                        }
                }
        }
        
        return 0;
}