贪心+构造，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;
}