poj3991(括号匹配-贪心)

题意：给一个长度为偶数的括号序列，问至少要改变多少个可以使得此括号序列合法；

解法：贪心的思想，遍历过程中如果前缀中有右括号没有匹配那么此右括号一定要变成左括号，如果右括号左边有没有匹配的左括号，则一定可以找左边最近的那个左括号匹配上。最后再加上剩余左括号数量的一半；

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;


char s[3000];
char stacks[3000];
int p=0;
int len=0;

int main()
{
    int t=0;cin>>t;
    int a=0;
  while(scanf("%s",s)==1)
  {
      if(s[0]==‘-‘)
        break;
      a++;
        p=0;
      int len=strlen(s);
      int ans=0;
      int left=0;
      for(int i=0;i<len;i++)
      {
          if(s[i]==‘{‘)
            left++;
          else
          {
              if(left>0)
                left--;
              else
                ans++,left=1;
          }
      }
      ans+=left/2;
      printf("%d. %d\n",a,ans);
  }
   return 0;
}
/*
[()][]([)[)
([)](])[
*/

poj3991(括号匹配-贪心),布布扣,bubuko.com

poj3991(括号匹配-贪心)

原文：http://blog.csdn.net/xiefubao/article/details/23396697