# 题目链接：
https://codeforces.com/contest/1097/problem/C
# 原题：
**Problem Statement**
One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.
A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.
Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.
This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?
**Input**
The first line contains one integer nn (1≤n≤1051≤n≤105) — the number of bracket sequences.
Each of the following nn lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".
The sum of lengths of all bracket sequences in the input is at most 5⋅1055⋅105.
Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.
**Output**
Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.
**Examples**
**input1**
7
)())
)
((
((
(
)
)
**output1**
2
**input2**
4
(
((
(((
(())
**output2**
0
**input3**
2
(())
()
**output3**
1
**Note**
In the first example, it's optimal to construct two pairs: "(( )())" and "( )".
------------
# 题意：
给你一堆括号字符串，问你能够成合法括号的对数，每一对合法括号仅可以使用没有被使用过的括号字符串中的两个，合法括号的定义这里就不解释了，就是C语言的括号机制。
# 思路：
对于每一个括号字符串，都有一个左配对值和右配对值，配对值的意思是在字符串中落单的，没有被匹配的括号的数目。左配对值就是“（”字符没有被匹配的数量，右配对值就是“）”字符没有被匹配的数量。
可以明白，对于左配对值和右配对值都不为零的情况下，是不能构成合法字符串的，因为两个括号字符串只能消去一个边的配对值。
因此，只要寻找map中是否有和当前括号字符串的配对值相互匹配就可以了（即左匹配值等于右匹配值，右匹配值等于左匹配值，且其中至少有一项为零）
# AC代码：
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
#include<map>
typedef long long ll;
#include<vector>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
#define debug() printf("haha\n")
const int MAXN =100005;
ll t,n,k;
ll a[MAXN];
ll ansa,ansb;
ll MIN=0x3f3f3f3f;
float fa,fb;
double da,db,dc,dlat,dans;
double dan[MAXN];
double eps=1e-6;
char ch;
int mpa[105][105];
int mpb[105][105];
std::string s,sb;
bool flag;
std::map< std::pair<ll,ll> ,int> mp;
int main()
{
cin(t);
for(int i=1;i<=t;i++)
{
std::cin>>s;
ll len=s.length();
ll zuo=0,you=0;
for(int j=0;j<len;j++)
{
if(s[j]=='(')
{
zuo++;
}
else
{
if(zuo!=0)
zuo--;
else
you++;
}
}
if(zuo!=0&&you!=0)
{
continue;
}
std::pair<ll,ll> a(zuo, you);
std::pair<ll,ll> b(you, zuo);
if(mp[b]!=0)
{
mp[b]--;
ansa++;
}
else
mp[a]++;
}
printf("%lld\n",ansa);
return 0;
}
```