求zhu！！，要求用c写

Question

Answer 1

思路
因为这个题目描述中，判断括号合法性的很方便的方法是用栈，所以我大概就先用栈去做。
一开始我的想法是，随便先抓两个放在一起，然后去判断匹不匹配。
判断匹配的时候我也是，只让左括号进栈，如果输进来一个右括号然后栈是空的那直接就爆炸。
但是，这方法必定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;
}