C. Yuhao and a Parenthesis

概述题目链接：http://codeforces.com/problemset/problem/1097/C   题意： 有n个只含有‘(‘和‘)‘的字符串，现在要字符串两两拼接，如果一个拼接后的字符串中的括号都配对了就称为完美匹配，问最多有几个完美匹配。(())就算一个完美匹配，))((或者())就不算。   思路： 我们能想到的是先让每一个字符串自己先匹配，比如(())((就相当于((，然后我们将

题目链接：http://codeforces.com/problemset/problem/1097/C

 

题意：

有n个只含有‘(‘和‘)‘的字符串，现在要字符串两两拼接，如果一个拼接后的字符串中的括号都配对了就称为完美匹配，问最多有几个完美匹配。(())就算一个完美匹配，))((或者())就不算。

 

思路：

我们能想到的是先让每一个字符串自己先匹配，比如(())((就相当于((，然后我们将所有的只含有一种括号的字符串存起来，因为如果是))((这种字符串的话不可能拼成完美匹配的字符串的，所以我们把所有的只含有一种括号的字符串存起来，对于((就只能和))拼接，就算一个完美匹配，然后就是去找一共有多少个完美匹配就好了，还有就是自身就是一个完美匹配的字符串也需要记录一下。思路大概就是这样，但是实现过程可能比较不太好想...

 1 #include <bits/stdc++.h> 2 #define maxn 500005 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 int n,yy; 6 map<int,int> m,p; 7 string str; 8   9 int main()10 {11     yy = 0;12     scanf("%d",&n);13     for(int i=0;i<n;i++){14         cin>>str;15         int len = str.length();16         int Min = 0;      // 防止出现))((的情况17         int xx = 0;       // 用来记录全是(或者)的数量18         for(int j=0;j<len;j++){19             if(str[j] == ‘(‘) xx ++;20             else xx --;21             Min = min(Min,xx);22         }23         if(Min == 0 && xx == 0){    // 表示自身就是一个完美匹配24             yy ++;25         }26         else if(Min == 0){          // 表示最终只剩(27             p[xx] ++;28         }29         else if(Min < 0 && Min == xx){   // 最终只剩)30             m[-xx] ++;31         }32     }33     int ans = yy / 2;             // 两个自身是完美匹配的串拼接为一个34     for(int i=0;i<maxn;i++){      // 遍历到最大值,求出括号相反却数量相同的个数35         ans += min(p[i],m[i]);36     }37     printf("%d\n",ans);38     return 0;39 }

总结

以上是内存溢出为你收集整理的C. Yuhao and a Parenthesis全部内容，希望文章能够帮你解决C. Yuhao and a Parenthesis所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。