C. Serval and Parenthesis Sequence

Link

Solution

要求一个每一个前缀都不是好括号串的好括号串。如果令“(”为+1，“)”为-1，则一个好括号串的和为0，所以现在就变成了求一个每一个前缀和都大于0且总和等于0的串。贪心地想，前面出现的+1越多越难小于0，但一个好括号串的左右括号数量是固定的n/2，所以可以从后往前补“)”，补够后剩下的（也就是之前的）“?”处全为左括号，最后再判一遍生成的括号序列是否为好括号串即可。

Code

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    int sum = 0, cnt = 0;
    if (n % 2) { cout << ":(" << endl; return 0; }
    for (int i = 0; i < n; i++)
        if (s[i] == ')')cnt++;
    cnt = n / 2 - cnt;//还需要补几个右括号
    for (int i = n - 1; i >= 0; i--) {
        if (cnt == 0)break;
        if (s[i] == '?')s[i] = ')', cnt--;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == ')') sum--;
        else s[i] = '(', sum++;
        if (sum < 0 || (i != n - 1 && sum == 0)) { cout << ":(" << endl; return 0; }
    }
    if (!sum) cout << s << endl;
    else cout << ":(" << endl;
    return 0;
}