为什么tle了
查看原帖
为什么tle了
107106
Paul张楼主2021/10/25 15:09
import java.util.*;
public class 回文
{
    static public void main(String[] args)
    {
        Scanner in= new Scanner(System.in);
        int t;
        t=in.nextInt();
        int [] a = new int [1000005];
        int n,head,tail,nn;
        int [] degwz = new int [1000005];
        int [] dygwz = new int [1000005];
        char [] fa = new char [1000005];
        int [] aa = new int [1000005];
        for(int ii=1;ii<=t;ii++)
        {
            n=in.nextInt();
            nn=0;
            for(int i=1;i<=n;i++)
            {
                dygwz[i]=0;
            }
            for(int i=1;i<=2*n;i++)
            {
                a[i]=in.nextInt();
                if(dygwz[a[i]]==0)
                {
                    dygwz[a[i]]=i;
                }
                else
                {
                    degwz[a[i]]=i;
                }
            }
            head=2;
            int uu,hh,tt;
            uu=1;
            tail=2*n;
            aa[1]=a[1];
            nn=degwz[a[1]];
            fa[1]='L';
            hh=nn+1;
            tt=nn-1;
            for(int i=2;i<=n;i++)
            {
                if(a[hh]==a[head]&&hh>=head)
                {
                    fa[i]='L';
                    aa[i]=a[head];
                    head++;
                    hh++;
                    uu++;
                    continue;
                }
                if(a[tt]==a[head]&&tt>head)
                {
                    fa[i]='L';
                    aa[i]=a[head];
                    head++;
                    tt--;
                    uu++;
                    continue;
                }
                if(a[hh]==a[tail]&&hh<tail)
                {
                    fa[i]='R';
                    aa[i]=a[tail];
                    tail--;
                    hh++;
                    uu++;
                    continue;
                }
                if(a[tt]==a[tail]&&tt<=tail)
                {
                    fa[i]='R';
                    aa[i]=a[tail];
                    tail--;
                    tt--;
                    uu++;
                    continue;
                }
            }
            if(uu==n)
            {
                for(int i=1;i<=n;i++)
                {
                    if(a[head]==aa[n-i+1])
                    {
                        fa[i+n]='L';
                        head++;
                    }
                    else
                    {
                        fa[i+n]='R';
                        tail--;
                    }
                }
                for(int i=1;i<=2*n-1;i++)
                {
                    System.out.print(fa[i]);
                }
                System.out.println('L');
                continue;
            }
            head=1;
            uu=1;
            tail=2*n-1;
            aa[1]=a[2*n];
            nn=dygwz[a[2*n]];
            fa[1]='R';
            hh=nn+1;
            tt=nn-1;
            for(int i=2;i<=n;i++)
            {
                if(a[hh]==a[head]&&hh>=head)
                {
                    fa[i]='L';
                    aa[i]=a[head];
                    head++;
                    hh++;
                    uu++;
                    continue;
                }
                if(a[tt]==a[head]&&tt>head)
                {
                    fa[i]='L';
                    aa[i]=a[head];
                    head++;
                    tt--;
                    uu++;
                    continue;
                }
                if(a[hh]==a[tail]&&hh<tail)
                {
                    fa[i]='R';
                    aa[i]=a[tail];
                    tail--;
                    hh++;
                    uu++;
                    continue;
                }
                if(a[tt]==a[tail]&&tt<=tail)
                {
                    fa[i]='R';
                    aa[i]=a[tail];
                    tail--;
                    tt--;
                    uu++;
                    continue;
                }
            }
            if(uu==n)
            {
                for(int i=1;i<=n;i++)
                {
                    if(a[head]==aa[n-i+1])
                    {
                        fa[i+n]='L';
                        head++;
                    }
                    else
                    {
                        fa[i+n]='R';
                        tail--;
                    }
                }
                for(int i=1;i<=2*n-1;i++)
                {
                    System.out.print(fa[i]);
                }
                System.out.println('L');
                continue;
            }
            System.out.println(-1);
        }
    }
}

2021/10/25 15:09
加载中...