题目大意
如果通过插入 “+”和 “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; }
评论
还没有任何评论,你来说两句吧!