HDU 5831 Rikka with Parenthesis II ——（括号匹配问题）

　　用一个temp变量，每次出现左括号，+1，右括号，-1；用ans来记录出现的最小的值，很显然最终temp不等于0或者ans比-2小都是不可以的。-2是可以的，因为：“))((”可以把最左边的和最右边的交换即可，其他-2的情形同理。另外要注意的坑点是Hint里面所说的：“But do nothing is not allowed.”。因此，“()”是不可以的，这个要特判。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <math.h>

 using namespace std;

 const int N =  + ;

 char s[N];

 int main()

 {

     int T;scanf("%d",&T);

     while(T--)

     {

         int n;scanf("%d",&n);

         scanf("%s",s+);

         if(strlen(s+)== && s[]=='(' && s[]==')')

         {

             puts("No");

             continue;

         }

         int temp = ;

         int ans = ;

         for(int i=;i<=n;i++)

         {

             if(s[i] == ')') temp --;

             else temp ++;

             ans = min(ans,temp);

         }

         if(ans<- || temp!=) puts("No");

         else puts("Yes");

     }

 }

巴特西

HDU 5831 Rikka with Parenthesis II ——（括号匹配问题）

最新文章

热门文章