codeforces1322A（括号匹配）

题意描述

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 l nanoseconds, where l 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 2 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.

可以排序括号内的元素，询问最小排序次数

思路

我们可以记录下第一个不匹配的括号位置，当能够出现和之前匹配的括号后，再计算即可

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=1005;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
void solve(){
	int n;cin>>n;
	string s;cin>>s;
	int cnt=0;
	rep(i,0,s.size()) s[i]=='(' ? cnt++ : cnt--;
	if(cnt) puts("-1");
	else{
		int ans=0,last=-1;
		rep(i,0,s.size()){
			if(s[i]=='(') cnt++;
			else cnt--;
			if(cnt<0 && last==-1) last=i;
			if(last!=-1 && !cnt){
				ans+=i-last+1;
				last=-1;
			}
		}
		cout<<ans<<endl;
	}
}
int main(){
    IOS;
    solve();
    return 0;
}