問題
https://codeforces.com/contest/1374/problem/C (新しいタブで開く)
問題文
長さ (偶数) の文字列 が与えられる。 は (
と )
のみからなる。 の中に含まれる (
の数と )
の数は同じ。
1 回の操作で、任意の 1 つの index について、その文字を先頭か末尾に移動する。
正しい括弧列にさせるための最小の操作回数は?
制約
サンプル
4 2 )( 4 ()() 8 ())()()( 10 )))((((())
1 0 1 3
考察
(
なら +1 、 )
なら -1 の累積和 (典型)
このとき、この累積和の最小値が答え。
前から順番に見ていくとき、この累積和がマイナスになったら、その )
を末尾に移動させることで、その時点までの和を +1 できるとみなせる (と思う)
コード
https://codeforces.com/contest/1374/submission/126805762 (新しいタブで開く)
void solve() { int n; cin >> n; string s; cin >> s; int dep = 0; int ans = 0; rep(i, n) { if (s[i] == '(') { dep++; } else { dep--; } if (dep < 0) { ans = min(ans, dep); } } cout << -ans << endl; }