求zhu！！，要求用c写

img

img

思路
因为这个题目描述中，判断括号合法性的很方便的方法是用栈，所以我大概就先用栈去做。
一开始我的想法是，随便先抓两个放在一起，然后去判断匹不匹配。
判断匹配的时候我也是，只让左括号进栈，如果输进来一个右括号然后栈是空的那直接就爆炸。
但是，这方法必定TLE，因为我当时都没想明白第二个用例为啥是1，感觉两个交换顺序也不一样啊，为啥是1.
后来DF才告诉我这句话是啥意思：
如果匹配上了相当于就被扔掉了，不会继续参与匹配。
但是由于括号是 类似于二进制的，因为只有左和右，所以不会出现
“A跟B，C能匹配，B跟C，D能匹配，C不能匹配D，但是由于我先把AB组合导致原来能匹配两组现在只能匹配一组”的情况
所以后来的想法大概是这样的：
把每个输入进来的括号序列先化简，去掉中间原本本来就能匹配的括号，最后只剩下四种情况：

全是左括号
全是右括号
有左有右
啥也不剩（自我匹配）
对于3，因为这个题只能随便抓出来两个进行匹配，所以只要是3这种情况的直接扔掉让他爬。
对于4，4这种必然不能和1，2去匹配，所以最后结果加上4这种情况出现的次数/2就行了。
对于1，2 因为肯定只能是同样数量的左（右）括号去匹配，所以对于每种 同样数量的 左（右）括号的情况，取他们的最小值即可。
例如：
假如“（（”有5个，“））”有3个，那最后结果+min(5,3) = 3即可。

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    //freopen("E://10.txt", "r", stdin);
    int T;
    //(是正的，)是负的。数字代表着拥有的个数
    int Kong = 0;
    int Left[100100] = { 0 };
    int Right[100100] = { 0 };
    cin >> T;
    while (T--)
    {
        char str[100100];
        cin >> str;
        int len = strlen(str);
        stack<char> s;
        int a = 0;
        int b = 0;
        for (int i = 0; i < len; ++i)
        {
            if (!s.empty())
            {//如果栈不是空的
                if (s.top() == '(' && str[i] == ')')
                {//恰好匹配
                    s.pop();
                    a--;
                }
                else if (s.top() == ')' && str[i] == '(')
                {//续上
                    s.push(str[i]);
                    a++;
                }
                else if (s.top() == ')' && str[i] == ')')
                {//续上
                    s.push(str[i]);
                    b++;
                }
                else if (s.top() == '(' && str[i] == '(')
                {//续上
                    s.push(str[i]);
                    a++;
                }
            }
            else if (s.empty())
            {//如果栈是空的
                if (str[i] == ')')
                {
                    s.push(str[i]);
                    b++;
                }
                else if (str[i] == '(')
                {
                    s.push(str[i]);
                    a++;
                }
            }
        }

        //判断完括号形式后进行统计
        if (s.empty())
        {//空的
            Kong++;
        }
        else if (a > 0 && b > 0)
        {
            continue;
        }
        else if (b == 0 && a > 0)
        {
            Left[a]++;
        }
        else if (a == 0 && b > 0)
        {
            Right[b]++;
        }

    }

    int ans = 0;
    ans += Kong / 2;
    for (int i = 0; i < 10010; i++)
    {
        if (Left[i] > 0 && Right[i] > 0)
        {
           ans+= min(Left[i], Right[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

#include<stdio.h>
#include<string.h>
int main()
{
    int n,i,j,p,sum=0,kind1=0,sl;
    int zuo[100000]={0},you[100000]={0},b[50000]={0},c[50000]={0};
    scanf("%d",&n);
    char a[100000];
     for(i=0;i<n;i++)
    {
        scanf("%s",a);
        sl=strlen(a);
        for(j=0;j<sl;j++)
        {
            if(a[j]=='(') zuo[i]++;
            else if(a[j]==')')
            {
                if(zuo[i]>0)  zuo[i]--;
                else if(zuo[i]==0)  you[i]++;
            }
        }
    }

    for(i=0,j=0,p=0;i<n;i++)
    {
       if(zuo[i]!=0&&you[i]==0) b[j++]=i;
        else if(zuo[i]==0&&you[i]!=0) c[p++]=i;
         else if(zuo[i]==0&&you[i]==0) kind1++;
    }

    for(i=0;i<j;i++)
    {
      for(n=0;n<p;n++)
        {
          if(zuo[b[i]]==you[c[n]])
           {
              sum+=1;
              you[c[n]]=-1;
              break;
           }
        }
    }
    printf("%d\n",sum+kind1/2);
}

img