正文索引 [隐藏]

传送门

题目大意

如果通过插入 “+”和 “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;
}