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;
}