括号序列操作专家

第一行包含一个整数 $T(1\leq T \leq 10^5)$ ，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 $n(1\leq n\leq 2\cdot 10^5)$ ，表示括号序列的长度。

第二行包含一个长度为 $n$ 的字符串，表示该括号序列。保证字符串只包含左括号 ` $\tt ($ ' 和右括号 ` $\tt )$ '。

保证对于所有的测试用例， $n$ 的总和不超过 $2\cdot 10^5$ 。

C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 800K, 提交时间: 2023-07-15 13:45:29

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
string s;
int sum,n,ans;
void solve(){
    cin>>n>>s;sum=ans=0;
    for(auto x:s){
        if(x=='(')sum++;
        else sum--;
        ans+=max(0ll,(1-sum)/2);
    }
    cout<<(sum?-1:ans)<<endl;
}
signed main(){
    int t=1;cin>>t;
    while (t--)solve();
}

Python3 解法, 执行用时: 222ms, 内存消耗: 5292K, 提交时间: 2023-07-22 20:20:26

import collections


n = int(input())

for _ in range(n):
    m = int(input())
    s = input()
    l , r = 0 , 0
    ans = 0
    for i , w in enumerate(s):
        if w == '(':
            l += 1
        else:
            r += 1
        if r > l and w == ')':
            ans += r - l
    ans = ans if l == r else -1
    print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 32ms, 内存消耗: 980K, 提交时间: 2023-07-22 13:06:02

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string c;
int main()
{
	int t;cin>>t;
	while(t--)
	{
		int n;cin>>n;cin>>c;
		ll zuo=0;ll sum=0;
		for(int i=0;i<n;i++)
		{
			if(c[i]=='(')zuo++;
			else {
			zuo--;if(zuo<0)sum-=zuo;
			}
		}
		if(zuo)cout<<-1<<endl;
		else cout<<sum<<endl;
	}
}

pypy3 解法, 执行用时: 189ms, 内存消耗: 25836K, 提交时间: 2023-07-14 21:21:00

for _ in range(int(input())):
    input()
    s = str(input())
    cnt, ans = 0, 0
    for c in s:
        if c == '(':
            ans += max(cnt, 0)
            cnt -= 1
        else:
            cnt += 1
    print(ans if cnt == 0 else -1)

详情