UESTC 764 失落的圣诞节 直接or线段树orRMQ

#include 
#include 
//#define LOCAL
using namespace std;
const int maxn=10000+8;
int N[maxn],S[maxn],Q[maxn],Sha,sum[maxn];


int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAK

    int T,n,maxN,mni,mni2,maxN3,mni3, maxSQ,mqsi, maxs, maxq;
    scanf("%d",&T);
    while(T--){
        maxN=0;maxSQ=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            {scanf("%d",&N[i]);if(maxN<N[i]) {maxN=N[i];mni=i;}  }
        for(int i=0;i<n;i++)
            scanf("%d",&S[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&Q[i]);
        for(int i=0;i<n;i++)
          {scanf("%d",&Sha);sum[i]=Sha+S[i]+Q[i];if(maxSQ<sum[i]) {maxSQ=sum[i];mqsi=i;}   }

        int max1=0,max2=0,max3=0, maxSQ2=0,maxN2=0;
        if(mni!=mqsi) max3=maxSQ+maxN;
        else{
            for(int i=0;i<n;i++)
                if(i!=mqsi) maxSQ2=max(maxSQ2,sum[i]);
            max1=maxN+maxSQ2;               //max0

            for(int i=0;i<n;i++)
                if(i!=mni) if(maxN2<N[i]) {maxN2=N[i];mni2=i;}
            max2=maxN2+maxSQ;
            max3=max(max1,max2);
        }

        int max4=0,max5=0,max6=0;

        maxs=0;maxq=0;
        for(int i=0;i<mni;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        for(int i=mni+1;i<n;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        max4=maxq+maxs+maxN;

        maxq=0;maxs=0;
        for(int i=0;i<mni2;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        for(int i=mni2+1;i<n;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        max5=maxq+maxs+maxN2;

        maxN3=0;
        for(int i=0;i<n;i++)
            if(i!=mni&&i!=mni2) if(maxN3<N[i]) {maxN3=N[i];mni3=i;}
        maxq=0;maxs=0;
        for(int i=0;i<mni3;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        for(int i=mni3+1;i<n;i++){
            maxq=max(maxq,Q[i]);
            maxs=max(maxs,S[i]);
        }
        max6=maxq+maxs+maxN3;

        printf("%d",max(max3,max(max4,max(max5,max6))));
        if(T) printf("n");
    }
    return 0;
}

没有用线段树，这里有3个要扫描的数组，再用数组建树，加上函数相对for(;;)的时间开销，时间复杂度差不多了，可能还会慢一点。

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx