2018 Multi-University Training Contest 1 | Balanced Sequence(暴力贪心)

转载自旧博客
传送门

今天这题,完全是我的锅,读错了题意(看成了有多少个匹配的字串)然后还决然的自己去敲了这道题,到了最后50mins在和队友关于算法完备性的争论中才发现自己读错了题……

最后再次5题gg,如果能早点发现读错题,6题兴许可能还能到第一页……

自己看题和解题思路还是不够明晰,想清楚了再去写,不然只能写bug.

然后这题,我们对四种偏序方式都进行一边排序,一次排序后贪心的时间复杂度为O(n)

#include<bits/stdc++.h>
using namespace std;
char s[100010];
 
 
struct edge
{
    int R,L;
}mi[100005];
 
void init()
{
    memset(mi,0,sizeof(mi));
}
 
bool cmp1(edge x,edge y)
{
    if(x.R!=y.R)
        return x.R>y.R;
    return x.L>y.L;
}
 
bool cmp2(edge x,edge y)
{
    if(x.R!=y.R)
        return x.R<y.R;
    return x.L>y.L;
}
 
bool cmp3(edge x,edge y)
{
    if(x.R!=y.R)
        return x.R<y.R;
    return x.L<y.L;
}
 
bool cmp4(edge x,edge y)
{
    if(x.R!=y.R)
        return x.R>y.R;
    return x.L<y.L;
}
 
int main()
{
    int T,n,m;
    while(scanf("%d",&T)!=EOF)
    {
        for(int t=1; t<=T; t++)
        {
            init();
            scanf("%d",&n);
            int ans=0,now=0;
            for(int i=1; i<=n; i++)
            {
                now=0;
                scanf("%s",s);
                int len=strlen(s);
                for(int j=0; j<len; j++)
                {
                    if(s[j]=='(')
                        now++;
                    else
                    {
                        if(now)now--,ans+=2;
                        else mi[i].L++;
                    }
                }
                mi[i].R=now;
            }
            if(n==1){
                printf("%d\n",ans);
                continue;
            }
            sort(mi+1,mi+1+n,cmp1);
            int MaxL=mi[1].L;
            int MaxR=mi[1].R;
            int Max=ans;
            int ANS=ans;
//            cout<<MaxL<<" "<<MaxR<<endl;
            for(int i=2;i<=n;i++)
            {
                if(min(mi[i].L,MaxR)>=min(mi[i].R,MaxL))
                {
                    ans+=2*min(mi[i].L,MaxR);
                    int add=min(mi[i].L,MaxR);
                    MaxR=MaxR-add+mi[i].R;
                    MaxL+=mi[i].L-add;
//                    cout<<min(mi[i].L,MaxR)<<endl;
                }
                else
                {
                    ans+=2*min(mi[i].R,MaxL);
                    int add=min(mi[i].R,MaxL);
                    MaxL=MaxL-add+mi[i].L;
                    MaxR+=mi[i].R-add;
//                    cout<<min(mi[i].R,MaxL)<<endl;
                }
            }
            Max=max(Max,ans);
            ans=ANS;
            sort(mi+1,mi+1+n,cmp2);
            MaxL=mi[1].L;
            MaxR=mi[1].R;
            for(int i=2;i<=n;i++)
            {
                if(min(mi[i].L,MaxR)>=min(mi[i].R,MaxL))
                {
                    ans+=2*min(mi[i].L,MaxR);
                    int add=min(mi[i].L,MaxR);
                    MaxR=MaxR-add+mi[i].R;
                    MaxL+=mi[i].L-add;
//                    cout<<min(mi[i].L,MaxR)<<endl;
                }
                else
                {
                    ans+=2*min(mi[i].R,MaxL);
                    int add=min(mi[i].R,MaxL);
                    MaxL=MaxL-add+mi[i].L;
                    MaxR+=mi[i].R-add;
//                    cout<<min(mi[i].R,MaxL)<<endl;
                }
            }
            Max=max(Max,ans);
            ans=ANS;
            sort(mi+1,mi+1+n,cmp3);
            MaxL=mi[1].L;
            MaxR=mi[1].R;
            for(int i=2;i<=n;i++)
            {
                if(min(mi[i].L,MaxR)>=min(mi[i].R,MaxL))
                {
                    ans+=2*min(mi[i].L,MaxR);
                    int add=min(mi[i].L,MaxR);
                    MaxR=MaxR-add+mi[i].R;
                    MaxL+=mi[i].L-add;
//                    cout<<min(mi[i].L,MaxR)<<endl;
                }
                else
                {
                    ans+=2*min(mi[i].R,MaxL);
                    int add=min(mi[i].R,MaxL);
                    MaxL=MaxL-add+mi[i].L;
                    MaxR+=mi[i].R-add;
//                    cout<<min(mi[i].R,MaxL)<<endl;
                }
            }
            Max=max(Max,ans);
            ans=ANS;
            sort(mi+1,mi+1+n,cmp4);
            MaxL=mi[1].L;
            MaxR=mi[1].R;
            for(int i=2;i<=n;i++)
            {
                if(min(mi[i].L,MaxR)>=min(mi[i].R,MaxL))
                {
                    ans+=2*min(mi[i].L,MaxR);
                    int add=min(mi[i].L,MaxR);
                    MaxR=MaxR-add+mi[i].R;
                    MaxL+=mi[i].L-add;
//                    cout<<min(mi[i].L,MaxR)<<endl;
                }
                else
                {
                    ans+=2*min(mi[i].R,MaxL);
                    int add=min(mi[i].R,MaxL);
                    MaxL=MaxL-add+mi[i].L;
                    MaxR+=mi[i].R-add;
//                    cout<<min(mi[i].R,MaxL)<<endl;
                }
            }
            Max=max(Max,ans);
            printf("%d\n",Max);
        }
    }
    return 0;
}