题解：CF1997C Even Positions

cfkk · 2024-07-31 08:00:31 · 题解

先甩个结论：如果序列中有 a 个左括号，那么答案为 2a+\dfrac{n}{2}。

以 n=8 为例。

首先，总距离最小的一定是 ()()()()。

然后，如果 ( 不在奇数点，就一定会出现下种情况 (())，并且此时，答案会增加 2。

因为题目中给出的是在偶数点的括号，所以直接算多出去的部分即可。

signed main()
{
    int T=read();
    while(T--)
    {
        int n=read(),cnt=0;
        for(int i=1;i<=n;i++)
        {
            char ch;
            cin>>ch;
            if(ch=='(')cnt++;
        }
        print(n/2+cnt*2);pc(1);
    }
    return 0;
}