CodeForces 3D. Least Cost Bracket Sequence

D. Least Cost Bracket Sequence
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output
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 ai and bi (1 ≤ ai,  bi ≤ 106), where ai is the cost of replacing the i-th character "?"with an opening bracket, and bi — 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.
Sample test(s) input (??) 1 2 2 8 output 4 ()()
欲張り法:カッコマッチングを考慮せずに、すべての疑問符を小さいカッコに設定します.
総括弧数が左括弧が多いか右括弧が多いかを確認します.
右括弧が多くなった場合:左括弧に交換する必要がある右括弧の数をnumbersとし、dataが左から右に循環し、左括弧sum++に遭遇した場合、右括弧sum--に遭遇し、sum<0がI左側で最適な右括弧を探して左括弧に交換した場合、sum+=2となる.
左かっこが多くなると、原理は同じで、dataが右から左に、sum>0であれば、最適な左かっこを探します.sum-=2です.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char data[50004];
int a[50004],b[50004],num[50004],len,cur;
long long sum;
int main(){
    endw:
    while(scanf("%s",data)!=EOF){
        sum=cur=0;
        int SumUnsure=0;
        len=strlen(data);

        for(int i=0;i<len;i++){
            if(data[i]=='(') { sum++;data[i]=1; }
            else if(data[i]==')') { sum--; data[i]=-1;}
            else if(data[i]=='?') {
                scanf("%d%d",&a[i],&b[i]);
                if(a[i]<=b[i]) {data[i]=1;SumUnsure++;}//<span style="color: rgb(34, 34, 34); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 19.6000003814697px;">              。</span>
                else if(b[i]<a[i]) {data[i]=-1;SumUnsure--;}
                num[cur++]=i;
            }
        }
        if(len%2==1) {printf("-1
");continue;}
        int type=0,numbers=0;
        if(SumUnsure+sum!=0){
            if(SumUnsure+sum<0) {type=-1;numbers=-(SumUnsure+sum)/2;}
            else {type=1;numbers=(SumUnsure+sum)/2;}
        }
        sum=0;
        if(type==-1||type==0){
        for(int I=0;I<len;I++){//          ，        
            sum+=data[I];
            if(sum<0) {
                int AminR_L=1000000,AminR_L_num;
                for(int j=0,i=num[0];i<=I&&j<cur;i=num[++j]){ //            
                    if(data[i]==-1&&AminR_L>a[i]-b[i]) {
                       AminR_L = a[i]-b[i];
                       AminR_L_num = i;
                    }
                }
                if(AminR_L==1000000) { printf("-1
");goto endw; }
                int AminL_R=1000000,AminL_R_num;
                if(numbers==0){
                    for(int j=cur-1,i=num[cur-1];i>I;i=num[--j]) { //            
                        if(data[i]==1&&AminL_R>b[i]-a[i]) {
                            AminL_R = b[i]-a[i];
                            AminL_R_num = i;
                        }
                        if(j<=0) break;
                    }
                    if(AminL_R==1000000) { printf("-1
");goto endw; }
                }
                else numbers--;

                if(AminL_R==1000000) {//numbers!=0
                    data[AminR_L_num] = -data[AminR_L_num];

                }
                else {
                    data[AminR_L_num] = -data[AminR_L_num];
                    data[AminL_R_num] = -data[AminL_R_num];
                }
                sum+=2;
            }
        }
        }
        else if(type==1){
        for(int I=len-1;I>=0;I--){//           ，        
            sum+=data[I];
            if(sum>0) {
                int Amin1=1000000,Amin1_num;

                for(int j=cur-1,i=num[cur-1];i>=I;i=num[--j]) { //            
                    if(data[i]==1&&Amin1>b[i]-a[i]) {
                        Amin1 = b[i]-a[i];
                        Amin1_num = i;
                    }
                    if(j<=0) break;
                }

                if(Amin1==1000000) { printf("-1
");goto endw; }

                int Amin2=1000000,Amin2_num;
                if(numbers==0){
                    for(int j=0,i=num[0];i<I;i=num[++j]){ //            
                        if(data[i]==-1&&Amin2>a[i]-b[i]) {
                            Amin2 = a[i]-b[i];
                            Amin2_num = i;
                        }
                        if(j>=cur-1) break;
                    }
                    if(Amin2==1000000) { printf("-1
");goto endw; }
                }
                else numbers--;
                if(Amin2==1000000) {//numbers!=0
                    data[Amin1_num] = -data[Amin1_num];
                }
                else {
                    data[Amin1_num] = -data[Amin1_num];
                    data[Amin2_num] = -data[Amin2_num];
                }
                sum-=2;
            }
        }
        }
        long long res=0;
        for(int i=0;i<cur;i++){
            int ID=num[i];
            if(data[ID]==1) res+=a[ID];
            else if(data[ID]==-1) res+=b[ID];
        }
        printf("%I64d
",res);
        for(int i=0;i<len;i++){
            if(data[i]==1) putchar('(');
            else if(data[i]==-1) putchar(')');
        }
        puts("");
    }
}