贪心+构造，CF1153 C. Serval and Parenthesis Sequence

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1153C - Codeforces

二、解题报告

1、思路分析

对于括号匹配问题我们经典做法是左括号当成1，右括号当成-1

那么只要任意前缀非负且最终总和为0那么该括号序列就是合法

对于本题，由于我们要保证任意前缀都不合法，所以任意严格前缀和都是正数（如果出现负数那么说明非法，如果为0则不满足本题要求）

所以前缀和要尽可能大

我们把'?’当成-1，预处理后缀和

遍历序列，如果当前sum + suf[i] < 0，说明我们还需添加左括号

否则添加右括号

如果中途存在sum <= 0且i != n -1说明非法

最后输出前如果sum != 0也说明无解

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;

std::ostream& operator<< (std::ostream& out, i128 x) {
    std::string s;
    while (x) s += ((x % 10) ^ 48), x /= 10;
    std::reverse(s.begin(), s.end());
    return out << s;
}

void solve() {
    int N;
    std::string s;
    std::cin >> N >> s;
    if (N & 1) {
        std::cout << ":(";
        return;
    }
    std::vector<int> suf(N + 1);
    std::unordered_map<char, int> mp;
    mp['('] = 1, mp[')'] = -1, mp['?'] = -1;
    for (int i = N - 1; ~i; i -- ) 
        suf[i] = suf[i + 1] + mp[s[i]];
    int sum = 0;
    for (int i = 0; i < N; i ++ ) {
        if (s[i] == '?') {
            if (sum + suf[i] < 0) sum ++, s[i] = '(';
            else sum --, s[i] = ')';
        }
        else 
            sum += mp[s[i]];
        if (sum <= 0 && i + 1 < N) {
            std::cout << ":(";
            return;
        }
    }
    if (!sum) std::cout << s;
    else std::cout << ":(";
}   

int main(int argc, char** argv) {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_ --)
        solve();
    return 0;
}