yukicoder 0022 平均の差

概要

対応の取れた, 括弧の列が与えられる. $k$ 番目の括弧と対応する括弧の場所を出力せよ.

制約

$1 \le n \le 10^4$

解法

括弧をスタックでごにょごにょする.

再帰してもいいけど, 多分そっちの方がめんどい.

$k$ 番目か答えのでかい方まで行ったらやめる事も出来るけど, たぶんそうしない方が楽.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
bool solve(){
    int n, k;
    cin >> n >> k; --k;
    string s; cin >> s;
    vector<int> st;
    vector<int> v(n);
    repsz(i, s){
        if(s[i] == '('){ st.eb(i); continue; }
        v[v[i] = st.back()] = i; st.pop_back();
    }
    cout << v[k]+1 << endl;
    return true;
}