双端队列20pts求调
查看原帖
双端队列20pts求调
362750
TernaryTree楼主2022/4/23 16:15
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e6 + 1;

int t, n, l, r, ind, k;
int p[maxn];
int q[maxn];
char s[maxn];

void init() {
	memset(p, 0, sizeof(p));
	memset(q, 0, sizeof(q));
	memset(s, 0, sizeof(s));
	ind = k = 0;
}

int main() {
	cin >> t;
	while (t--) {
		bool fl = 1;
		init();
		cin >> n;
		l = 1, r = 2 * n;
		deque<int> a, b;
		for (int i = 1, flag = -1; i <= 2 * n; i++) {
			cin >> p[i];
			if (p[i] == p[1]) {
				flag++;
				continue;
			}
			if (flag == 0) a.push_back(p[i]);
			else b.push_front(p[i]);
		}
		s[++ind] = 'L';
		while (!a.empty() || !b.empty()) {
			if (!a.empty() && !b.empty()) {
				if (a.back() == b.front()) {
					a.pop_back();
					b.pop_front();
					s[++ind] = 'L';
					continue;
				} else if (a.back() == a.front()) {
					a.pop_back();
					a.pop_front();
					s[++ind] = 'L';
					continue;
				} else if (b.back() == a.front()) {
					b.pop_back();
					a.pop_front();
					s[++ind] = 'R';
					continue;
				} else if (b.back() == b.front()) {
					b.pop_back();
					b.pop_front();
					s[++ind] = 'R';
					continue;
				} 
			} else if (!a.empty()) {
				if (a.back() == a.front()) {
					a.pop_back();
					a.pop_front();
					s[++ind] = 'L';
					continue;
				}
			} else if (!b.empty()) {
				if (b.back() == b.front()) {
					b.pop_back();
					b.pop_front();
					s[++ind] = 'R';
					continue;
				}
			}
			cout << -1 << endl;
			fl = 0;
			break;
		}
		if (!fl) continue;
		for (int i = 1; i <= ind; i++) {
			if (s[i] == 'L') {
				q[++k] = p[l++];
			} else {
				q[++k] = p[r--];
			}
		}
		for (int i = 1; i <= n; i++) {
			if (p[l] == q[n - i + 1]) {
				q[i + n] = p[l++];
				s[++ind] = 'L';
			} else {
				q[i + n] = p[r--];
				s[++ind] = 'R';
			}
		}
		for (int i = 1; i <= 2 * n; i++) {
			cout << s[i];
		}
	}
	return 0;
}
2022/4/23 16:15
加载中...