正文索引 [隐藏]

传送门

题目大意

如果通过插入 “+”和 “1 “可以从中得到一个形式完整的数学表达式,那么一个带括号的序列 就被称为正确。例如,”(())()”、”() “和”(()())) “等序列是正确的,而”)(“、”(()) “和”(()))(“则不正确。

老师给德米特里的班级布置了一个非常奇怪的任务:她要求每个学生想出一个任意长度的序 列,只由开头和结尾的括号组成。之后,所有学生轮流说出自己想出的序列。

轮到迪马时,他突然发现,所有同学都得到了正确的括号序列,而他是否得到了正确的括号序列,他不知道。 迪马现在怀疑自己只是漏掉了任务书中的 “正确 “二字,所以现在他想通过稍微修改自己的序 列来挽救局面。更准确地说,他可以任意次数(可能是零)地执行重排序操作。

重排序操作包括选择序列中任意一个连续的子串,然后以任意的方式对其中的所有字符进行重 排序。这种操作需要l纳秒,其中l是被重新排序的子段的长度。很容易看出,重新排序操作并 不会改变开括号和收括号的数量。例如对于”))((“,他可以选择子串”)(“,然后进行重排 序”)()(“(这个操作需要2纳秒)。

由于Dima很快就要回答,他想尽快让自己的序列正确。帮助他做到这一点,或者确定这是不可能的。

输入输出

输入

第一行包含一个整数n(1≤n≤10e6)表示序列的长度。 第二行包含长度为n的字符串,仅由字符”(“和”) “组成。

输出

打印一个整数:使序列正确的最小纳秒数,如果不可能做到,则打印”-1″。


难度不大的栈括号,遇到左括号就压进去,右括号弹,如果栈不空就输出-1,否则输出答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
string s;
int	ans, cnt;

int main()
{
	cin >> n >> s;
	for ( int i = 0; i < n; i++ )
	{
		if ( s[i] == ')' )
			cnt++;
		else
		{
			cnt--;
			if ( cnt >= 0 )
				ans++;
		}
	}
	if (cnt == 0)//空 
		cout << ans * 2 << endl;
	else
		cout << -1 << endl;
	
	return 0;
}