正式赛1011 合法匹配

Problem Description

括号序列指的是只包含 ‘(’ 和 ‘)’ 的序列。
合法括号序列的定义如下:
1.空序列为合法序列。
2.如果 A 是一个合法序列,则 (A) 也为合法序列。
3.如果 A 和 B 都为合法序列,则 AB 也为合法序列。
现给出一个括号序列,求最少删去几个括号能得到一个合法序列。

Input

第一行一个整数 T(1≤T≤30) ,表示测试数据组数。接下来包含 T 组测试数据。

对于每组测试数据,第一行输入一个整数 n (1≤n≤2×105) ,表示括号序列的长度。

第二行输入一个长为 n 的括号序列。

Output

对于每组测试数据,输出一个数表示最少删去几个括号能得到一个合法的括号序列。

Sample Input

2
6
()(())
7
())(()(

Sample Output

0
3

仔细读题,理解题意。

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,index=0;
        scanf("%d",&n);
        getchar();
        char str[n];
        char a;
        for(int i=0;i<n;i++)
        {
            a=getchar();
            if(index==0)
            {
                str[index]=a;
                index++;
                //cout<<"index1:"<<index<<"str_top1:"<<str[index-1]<<endl;  //测试所用
            }else{
                if(a=='(')
                {
                    str[index]=a;
                    index++;
                }else if(a==')'){
                    if(str[index-1]=='(')
                    {
                        str[index-1]='0';
                        //cout<<"str_top:"<<str[index-1]<<endl;  //测试所用
                        index--;
                    }else{
                        str[index]=a;
                        index++;
                    }
                }
            }
        }
        printf("%d\n",index);
    }
    return 0;
}

上一篇:leetcode 1011. 在 D 天内送达包裹的能力


下一篇:使用js加载器动态加载外部js、css文件