CF3D Least Cost Bracket Sequence（贪心）

题目链接

题意简述

有一个长为 $n$ 的括号序列，其中一些位置是问号，每个问号替换成左括号或替换成右括号各有给定的代价，判断是否能够构造出一个合法的括号序列，如果可以，求出最小代价。

$n \leq 5 \cdot 10^{4}$ （实际上可以大很多）。

简要做法

考虑使用带反悔的贪心。

如果用 $c n t [i]$ 表示 $\sum_{j = 1}^{i} (- 1)^{[a_{i} =^{'})^{'}]}$ （左括号比右括号多的个数），括号序列合法当且仅当 $\forall i, c n t [i] \geq 0$ 且 $c n t [n] = 0$ 。

如果把右括号反悔成左括号，一定可以保证 $c n t [i] \geq 0$ 这个条件依然满足。

但是，如果把左括号反悔成右括号，有可能造成本来 $c n t [i] \geq 0$ 的位置小于 $0$ 。

并且，如果选择了多余的左括号，还会导致 $c n t [n] > 0$ 。

如何解决这些问题呢？

可以发现，如果初始时优先选择右括号，上述问题就都得到解决了。

即，每次碰到问号都选右括号，并且将其标记为可以反悔为左括号。如果 $c n t [i] < 0$ ，就从可反悔的右括号里选反悔代价最小的改成左括号。这样的话， $c n t [i] \geq 0$ 不会因反悔而被破坏， $c n t [n] > 0$ 也不会在有解时发生。

具体实现可以用堆（priority_queue）。

参考代码

复制
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int N = 50010;
 
int n;
char s[N];
long long ans;
priority_queue<pii, vector<pii>, greater<pii> > q;
 
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    
    int cnt = 0;
    
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '(') ++cnt;
        else if (s[i] == ')') --cnt;
        else
        {
            int a, b;
            scanf("%d%d", &a, &b);
            --cnt;
            s[i] = ')';
            ans += b;
            q.push(pii(a - b, i));
        }
        if (cnt < 0)
        {
            if (q.empty()) break;
            cnt += 2;
            ans += q.top().first;
            s[q.top().second] = '(';
            q.pop();
        }
    }
    
    if (cnt == 0) printf("%I64d\n%s", ans, s + 1);
    else puts("-1");
    
    return 0;
}

文章目录

题目链接

题意简述

简要做法

参考代码