本文共 2843 字,大约阅读时间需要 9 分钟。
C. Unusual Competitions
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
A bracketed sequence is called correct (regular) if by inserting "+" and "1" you can get a well-formed mathematical expression from it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not.
The teacher gave Dmitry's class a very strange task — she asked every student to come up with a sequence of arbitrary length, consisting only of opening and closing brackets. After that all the students took turns naming the sequences they had invented. When Dima's turn came, he suddenly realized that all his classmates got the correct bracketed sequence, and whether he got the correct bracketed sequence, he did not know.
Dima suspects now that he simply missed the word "correct" in the task statement, so now he wants to save the situation by modifying his sequence slightly. More precisely, he can the arbitrary number of times (possibly zero) perform the reorder operation.
The reorder operation consists of choosing an arbitrary consecutive subsegment (substring) of the sequence and then reordering all the characters in it in an arbitrary way. Such operation takes ll nanoseconds, where ll is the length of the subsegment being reordered. It's easy to see that reorder operation doesn't change the number of opening and closing brackets. For example for "))((" he can choose the substring ")(" and do reorder ")()(" (this operation will take 22 nanoseconds).
Since Dima will soon have to answer, he wants to make his sequence correct as fast as possible. Help him to do this, or determine that it's impossible.
Input
The first line contains a single integer nn (1≤n≤1061≤n≤106) — the length of Dima's sequence.
The second line contains string of length nn, consisting of characters "(" and ")" only.
Output
Print a single integer — the minimum number of nanoseconds to make the sequence correct or "-1" if it is impossible to do so.
Examples
input
Copy
8))((())(
output
Copy
6
input
Copy
3(()
output
Copy
-1
Note
In the first example we can firstly reorder the segment from first to the fourth character, replacing it with "()()", the whole sequence will be "()()())(". And then reorder the segment from the seventh to eighth character, replacing it with "()". In the end the sequence will be "()()()()", while the total time spent is 4+2=64+2=6 nanoseconds.
【方法】
括号匹配遇到好几次了,,但每次好像都没有通法,,题目要求变成匹配的括号,,给未匹配的排序,,已经匹配的不用排了,首先如果左右括号不相等的话肯定不行,,考虑当前字符是否是’(’,如果是的话,看栈顶元素是否是’)’,如果是的话,这说明可以将这两个字符排序可以正确匹配,所以我们将sum++,并且删除栈顶元素;不是的话就将’(‘入栈。
如果当前元素是’)’ ,看栈顶是否是’('是的话就删除栈顶元素(因为这个是已经排好了,不用动了);否则入栈。#includeusing namespace std;int cnt[2];int main(){ ios::sync_with_stdio(false); int n; cin>>n; string s; cin>>s; stack q; for(int i=0;i
转载地址:http://styzi.baihongyu.com/