40分双端队列做法求调
查看原帖
40分双端队列做法求调
600441
ZhongYuLin楼主2023/9/17 11:27

rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;
int a[maxn],T,n,tot,l1,r1,l2,r2;//双端队列做法l1~r1是左侧队列,l2~r2是右侧队列 
char b[maxn],c[maxn];

int main(){
	cin>>T;
	while(T--){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		cin>>n;
		for(int i=1;i<=n*2;i++)
			scanf("%d",&a[i]);
		for(int i=2;i<=n*2;i++)
			if(a[i]==a[1]){
				r1=i;l2=i+1;
				break;
			}
		tot=0;l1=1;r2=2*n;
		while(tot<n){
			if(l1<r1&&a[l1]==a[r1]){
				l1++;r1--;
				b[++tot]='L';
				c[tot]='L';
			}
			else if(l1<=r1&&l2<=r2&&a[l1]==a[l2]){
				l1++;l2++;
				b[++tot]='R';
				c[tot]='L';
			}else if(l1<=r1&&l2<=r2&&a[r2]==a[r1]){
				r2--;r1--;
				b[++tot]='L';
				c[tot]='R';
			}
			else if(l2<r2&&a[r2]==a[l2]){
				r2--;l2++;
				b[++tot]='R';
				c[tot]='R';
			}
			else{
				printf("-1");
				goto out;
			}
			//printf("%d %d %d %d\n",l1,r1,l2,r2);
		}
		for(int i=1;i<=tot;i++)
			cout<<c[i];
		for(int i=tot;i>=1;i--)
			cout<<b[i];
		out:;
		puts("");
	}
	return 0;
} 
2023/9/17 11:27
加载中...