[CF3D] Least Cost Bracket Sequence

[CF3D] Least Cost Bracket Sequence - 贪心,堆

Description

给一个序列，序列里面会有左括号、问号、右括号。对于一个‘？’而言，可以将其替换为一个‘（’，也可以替换成一个‘）’，但是都有相应的代价，且对于没一个 '?' 而言代价未必是相同的。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

Solution

首先考虑，将所有 ? 都变成 )，用 mark 记录当前剩余的左括号的数量

如果出现了 mark 小于 0 的情况，我们到前面去找一个 ? 变成 ) 来改为 (，并将 mark +2

这样，合法的情况是可以构造出来的

为了使得代价最小，我们应该寻找 -b+a 最小者进行替换

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    string s;
    int a, b, c = 0, ans = 0;
    priority_queue<pair<int, int>> que;

    cin >> s;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
        {
            ++c;
        }
        else if (s[i] == ')')
        {
            --c;
        }
        else
        {
            cin >> a >> b;
            s[i] = ')';
            --c;
            que.push({b - a, i});
            ans += b;
        }
        if (c < 0)
        {
            if (que.size())
            {
                auto [v, id] = que.top();
                que.pop();
                ans -= v;
                s[id] = '(';
                c += 2;
            }
            else
            {
                cout << -1;
                return 0;
            }
        }
    }

    if (c == 0)
    {
        cout << ans << endl
             << s << endl;
    }
    else
    {
        cout << -1;
    }
}