题解：AT_arc175_b [ARC175B] Parenthesis Arrangement

tXX_F · 2024-04-01 12:52:33 · 题解

Parenthesis Arrangement

解题思路

先用一个字符串顺序存下不符合题目要求的括号，然后分别记录下其中左括号和有括号的数量。如果交换括号对的代价小于改变一对括号的代价，即 A < B \times 2，那么就交换否则替换。若交换后仍然有剩余的括号，则只能进行替换。若剩下的左括号数量不为 2 的倍数，则须再单独取出一个括号替换。

AC Code

#include <bits/stdc++.h>
using namespace std;
long long N, A, B;
string S;
long long Answer;
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cin >> N >> A >> B >> S;
    string s;
    for (int i = 0, count_left = 0; i < S.size(); i++) {
        if (S[i] == '(') count_left++, s.push_back('(');
        if (S[i] == ')') if (count_left >= 1) count_left--, s.pop_back();
            else s.push_back(')');
    }
    long long left_count = 0, right_count = 0;
    for (int i = 0; i < s.size(); i++) if (s[i] == '(') left_count++;
        else if (s[i] == ')') right_count++;
    if (left_count && right_count && A < B * 2) {
        int _min = min(left_count, right_count);
        Answer += _min / 2 * A;
        if (_min % 2 == 1) Answer += A;
        left_count -= _min, right_count -= _min;
    }
    if (left_count) Answer += left_count / 2 * B;
    if (right_count) Answer += right_count / 2 * B;
    if (left_count & 1) Answer += 2 * B;
    cout << Answer << endl;
    return 0;
}