贪心 D. Least Cost Bracket Sequence

Problem - D - Codeforces

题目大意：给一个只包含(，)，?三个字符的字符串。每个?可以转为(或者)，对于第$i$个?转为(需要花费$a_i$，转为)需要花费$b_i$。现在问能否让该字符串转为合法的括号匹配，如果可以找到最小花费并输出转为的括号匹配。

思路：?的情况可以转为(，也可以转为)，是动态的，处理起来麻烦。我们可以将?全都先转为同一种，记录总花销，之后根据情况替换为另一个，这样虽然也是动态的，但是要维护的状态少了很多。

在此，将?先全部转为)，对于中间态而言，左边(可以多，但是)数量一定小于等于左边。用括号匹配的类似操作进行计数，(进行累加计数，对于其他的，如果是?先贪心的转为)，之后让计数减一。根据计数值进行贪心的更改：将原来?转)的替换为(，并将计数值和字符串状态进行更新。贪心的时候需要找到中间值$i$前面的?中$a_i-b_i$最小那个?进行转换。

代码如下：

void solve() {string s; cin>>s;priority_queue<PII> heap;int n = s.size();vector<array<int,2>> a(n); // (val, )valint ans = 0;// 先得到 ? -> ) 的总花销for(int i = 0; i < n; ++i) {if(s[i] == '?') {cin>>a[i][0]>>a[i][1];ans += a[i][1];}}// 判断括号序列是否合法bool ok = 1;int cnt = 0; // 计数for(int i = 0; i < n; ++i) {if(!ok) break;if(s[i] == '(') cnt++;else {// 如果不是 ( 优先转为 ) ，并计算差值，cnt--;if(s[i] == '?') heap.push({a[i][1] - a[i][0], i}), s[i] = ')';// 如果是计数是负数// 将前面的 ( ? -> ) ) -> ( 转为 (// 并更新计数和字符串值if(cnt < 0) {if(heap.size() == 0) ok = 0;else {auto tmp = heap.top(); heap.pop();ans -= tmp.first;cnt += 2;s[tmp.second] = '(';}}}}if(cnt || !ok) puts("-1");else {cout<<ans<<'\n';cout<<s<<'\n';}
}