D. Least Cost Bracket Sequence （贪心）

妖狐艹你老母 2022-06-18 09:07 118阅读 0赞

[点击打开链接][Link 1]

http://codeforces.com/contest/3/problem/D

D. Least Cost Bracket Sequence

**Description：**

This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "\+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

Input

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow *m* lines, where *m* is the number of characters "?" in the pattern. Each line contains two integer numbers *a**i* and *b**i* (1 ≤ *a**i*,  *b**i* ≤ 106), where *a**i* is the cost of replacing the *i*\-th character "?" with an opening bracket, and *b**i* — with a closing one.

Output

Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print \-1, if there is no answer. If the answer is not unique, print any of them.

Examples

input

(??)
    1 2
    2 8

output

4
    ()()

题意：

给你一个序列，序列里面有左括号，右括号。对于一个“？”，可以替换成“（”，“）”，替换的代价为a\_i，b\_i。

问你如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出-1。

解释样例：

对于第一个括号，那就替换成“）”，代价为2。

对于第二个括号，那就替换成“（”，代价为2。

所以最少总代价为2+2=4。

题解：贪心。

每遇到一个‘？’，就替换成右括号，并维护一个计数器count，当遇到左括号时计数器+1，遇到右括号时计数器-1。如果中途遇到count小于0的情况，则说明这个序列不是括号匹配的，而多余的右括号可能是‘？’变来的，所以当遇到count小于0时，则去看前面有没有‘？’变过来的右括号，如果没有，那就说明无论如何这个序列无法被替换为括号匹配的序列；如果有的话，则选取一个花费最少代价变来的右括号，将其改为左括号，这样的话count就要加2了。如果这样到最后count还大于0，则说明即使无法获得一个括号匹配的序列，输出-1即可。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxx=50010;
    char s[maxx];
    set<pair<long long,int> >st;
    int main()
    {
        scanf("%s",s);
        long long count=0,ans=0;
        for(int i=0;s[i];i++)
        {
            if(s[i]=='(')count++;
            else if(s[i]==')')count--;
            else
            {
                int a,b;
                cin>>a>>b;
                ans+=b;
                s[i]=')';
                count--;
                st.insert(make_pair(a-b,i));
            }
            while(count<0)
            {
                if(st.empty())return 0*printf("-1");
                ans+=st.begin()->first;
                s[st.begin()->second]='(';
                st.erase(st.begin());
                count+=2;
            }
        }
        if(count>0)printf("-1");
        else printf("%lld\n%s",ans,s);
        return 0;
    }

[Link 1]: http://codeforces.com/contest/3/problem/D