题解：P14172 【MX-X23-T2】括号串

a_gold_TomAndJerry · 2025-10-06 19:01:41 · 题解

考场上因为认为括号可以改无限次被这道题硬控了。

题目大意：给你一个括号串，判断它是否合法，若不合法就把一对相反的括号改正再次检查。

直接在原字符串上模拟即可。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,t;
    string s;
    scanf("%d",&t);
    while(t--){
        cin>>n>>s;
        int bal=0;
        bool flag=1;
        for(int i=0;i<n;++i){
            if(s[i]=='(') bal++;
            else bal--;
            if(bal<0) flag=0;
        }
        if(flag&&bal==0){
            cout<<"Yes"<<'\n';
            continue;
        }
        if(bal!=0){
            cout<<"No"<<'\n';
            continue;
        }
        int pos=-1;
        for(int i=0;i<n;++i){
            if(s[i]=='(') bal++;
            else bal--;
            if(bal<0){
                pos=i;
                break;
            }
        }
        if(pos!=-1&&pos<n-1){
            swap(s[pos],s[pos+1]);
            bal=0;
            flag=1;
            for(int i=0;i<n;++i){
                if(s[i]=='(') bal++;
                else bal--;
                if(bal<0){
                    flag=0;
                    break;
                }
            }
            if(flag&&bal==0){
                cout<<"Yes"<<'\n';
                continue;
            }
        }
        cout<<"No"<<'\n';
    }
    return 0;
}