[数据结构与算法]找到牛（春季每日一题 35）

奶牛贝茜逃跑了，躲在了长满高草的山脊上。

农夫约翰为了抓回贝茜，决定在草地中匍匐前行，从而不被贝茜发现。

不幸的是，发现贝茜并没有那么容易。

约翰面前的草看起来像是一个长度为 $N$ 的括号字符串，例如：

)((()())())

约翰清楚贝茜的后腿看上去就像一对相邻的左括号 ((，她的前腿看上去就像一对相邻的右括号 ))。

因此，贝茜的位置可以用一对索引 $x<y$ 来描述，使得 (( 在位置 $x$ 处被找到，)) 在位置 $y$ 处被找到。

请计算贝茜可能站立的不同位置的数量。

输入格式
共一行，包含一个长度为 $N$ 的括号字符串。

输出格式
输出贝茜可能站立的不同位置的数量。

数据范围
$1\le N\le 50000$

输入样例：

)((()())())

输出样例：

4

样例解释
$4$ 种可能的站立位置如下所示：

1. )((()())())
    ^^   ^^

2. )((()())())
     ^^  ^^

3. )((()())())
     ^^     ^^

4. )((()())())
    ^^      ^^

#include<iostream>

using namespace std;

const int N = 50010;

string s;

int main(){
    
    cin >> s;
    
    int a = 0, b = 0;
    
    for(int i = 1; i < s.size(); i++)
        if(s[i] == '(' && s[i] == s[i - 1]) a++;
        else if(s[i] == ')' && s[i] == s[i-1]) b += a;
        
    cout << b << endl;
    
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖