双端队列过不了编译,求调
查看原帖
双端队列过不了编译,求调
582900
JerryMain楼主2022/10/23 22:51
#include "iostream"
#include "queue"
using namespace std;
const int maxn=5e5+1;
int a[maxn*2];
char b[maxn*2];
int t,n,p;
void print()
{
    for(int i=1;i<=n;i++)
        cout<<b[i]<<" ";
    cout<<endl;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        n=n*2;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        //1.L first
        b[1]='L',b[n]='L';
        p=2;
        deque<int> q1,q2;
        while(a[p]!=a[1])
            q1.push_back(a[p++]);
        p++;
        while(p<=n)
            q2.push_back(a[p++]);
        p=2;
        while(true)
        {
            //LL
            if(!q1.empty()&&q1.size()>1&&(q1.front() == q1.back()))
            {
                b[p]='L';
                b[n-p+1]='L';
                q1.pop_front();
                q1.pop_back();
                continue;
            }
            //LR
            if(!q1.empty()&&!q2.empty()&&q2.size()>1&&q1.size()>1&&(q1.begin() == q2.begin()))
            {
                b[p]='L';
                b[n-p+1]='R';
                q1.pop_front();
                q2.pop_front();
                continue;
            }
            //RL
            if(!q2.empty()&&!q1.empty()&&q1.size()>1&&q2.size()>1&&(q1.back() == q2.begin()))
            {
                b[p]='R';
                b[n-p+1]='L';
                q1.pop_back();
                q2.pop_front();
                continue;
            }
            //RR
            if(!q2.empty()&&q2.size()>1&&(q2.front() == q2.back()))
            {
                b[p]='R';
                b[n-p+1]='R';
                q2.pop_front();
                q2.pop_back();
                continue;
            }
        }
        if(q1.empty()&&q2.empty())
        {
            print();
            continue;
        }
        //2.R first
        b[1]='R',b[n]='L';
        p=1;
        deque<int> q11,q22;
        while(a[p]!=a[n])
            q11.push_back(a[p++]);
        p++;
        while(p<=n-1)
            q22.push_back(a[p++]);
        p=1;
        while(true)
        {
            //LL
            if(!q11.empty()&&q11.size()>1&&(q11.begin() == q11.back()))
            {
                b[p]='L';
                b[n-p+1]='L';
                q11.pop_front();
                q11.pop_back();
                continue;
            }
            //LR
            if(!q11.empty()&&!q22.empty()&&q22.size()>1&&q11.size()>1&&(q11.begin() == q22.begin()))
            {
                b[p]='L';
                b[n-p+1]='R';
                q11.pop_front();
                q22.pop_front();
                continue;
            }
            //RL
            if(!q22.empty()&&!q11.empty()&&q11.size()>1&&q22.size()>1&&(q11.back() == q22.begin()))
            {
                b[p]='R';
                b[n-p+1]='L';
                q11.pop_back();
                q22.pop_front();
                continue;
            }
            //RR
            if(!q22.empty()&&q22.size()>1&&(q22.front() == q22.back()))
            {
                b[p]='R';
                b[n-p+1]='R';
                q22.pop_front();
                q22.pop_back();
                continue;
            }
        }
        if(q11.empty()&&q22.empty())
        {
            print();
            continue;
        }
        //3.no way
        cout<<"-1"<<endl;
    }
}

2022/10/23 22:51
加载中...