京东9.3编程最后一题O(n)做法

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    string str;
    cin >> str;

    vector<int> count_vec;  // 如())())的count_vec为{1, 2, 1, 2}
    count_vec.emplace_back(1);
    for(int i = 1; i < str.size(); i++){
        if(str[i] == str[i - 1]) count_vec.back()++;
        else count_vec.emplace_back(1);
    }

    long long res = 0, weight = 0, count = count_vec[0];
    char last_char = str[0];
    
    for(int i = 1; i < count_vec.size(); i++){
        if(last_char == '('){
            last_char = ')';
            weight += 2 * count;
        }
        else last_char = '(';
        res += weight * count_vec[i];
        count += count_vec[i];
    }

    cout << res;

    return 0;
}