Acwing / 2004. Mauvaise écriture

Explication du problème

Objet du sujet：

• Conditions1：Pour tout préfixe de chaîne,Inclus dans ( Pas moins de ) Nombre de.

• Conditions2：La chaîne saisie satisfait：Modifier un seul caractère au maximum,Peut devenir une chaîne de parenthèses équilibrée.

La question se limite donc à la nécessité de changer une parenthèse pour correspondre à la séquence！

Idées de conclusion：

• Classification：1.Nombre de Parenthèses gauche et droiteR LMême chose.;2.La parenthèse droite doit être convertie en parenthèse gauche：R=L+2;La parenthèse gauche doit être convertie en parenthèse：L=R+2

• Type①：Produits0Direct

• Type②：Enregistrer de gauche à droite pour chaque emplacement Préfixes et,Par Condition1Oui.：.Rechercher de gauche à droite la position de la première parenthèse gauche qui est inférieure à la parenthèse droite, La position et l'une des parenthèses de droite précédentes sont changées en parenthèses de gauche pour satisfaire à la condition1,.Les réponses sont préfixées par des parenthèses droites à cet endroit et

• Type③：Enregistrer de droite à gauche pour chaque emplacement Préfixes et,Par Condition1Oui.：Rechercher de droite à gauche la position de la première parenthèse droite qui est inférieure à la parenthèse gauche,Cette position et l'une des parenthèses d'ouverture à droite peuvent être changées en parenthèses d'ouverture pour satisfaire à la condition1,Les réponses sont préfixées par des parenthèses ouvertes à cet endroit et

#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}; // Préfixe et
        int sumR[n+1] = {
    0};
        if(L == R){
    
                cout<<0<<endl;
        }else if(L < R){
    
                // La parenthèse droite doit être convertie en parenthèse gauche：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;
                        // Jugement  Position de la première parenthèse gauche inférieure à la parenthèse droite 
                        if(arr[i] == ')' and sumL[i+1] < sumR[i+1]){
    
                                cout<<sumR[i+1]<<endl;
                                break;
                        }
                }
        }else{
    
                // La parenthèse gauche doit être convertie en parenthèse：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;
                        // Jugement  La position de la première parenthèse droite est inférieure à celle de la parenthèse gauche 
                        if(arr[i] == '(' and sumL[i] > sumR[i]){
    
                                cout<<sumL[i]<<endl;
                                break;
                        }
                }
        }
        
        return 0;
}