洛谷 P1155

题目链接:P1155 双栈排序

题目大意

利用两个栈是原序列从小到大输出

solution

我们可以先考虑一个栈, 那我们怎么考虑呢?

2 3 1 的话, 只能输出1 3 2, 其余的5种都为 1 2 3 所以我们考虑这个性质, 然后如果如果不行,就放到二分图的另一个点,然后二分图染色就做完了

Code:

/**
*    Author: Alieme
*    Data: 2020.9.1
*    Problem: P1155
*    Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define int long long
#define rr register

#define inf 1e12
#define MAXN 2010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

struct Stack {
	int s[MAXN], tot;
	inline void push(int x) {s[++tot] = x;}
	inline void pop() {tot--;}
	inline int top() {return s[tot];}
	inline bool empty() {return tot <= 0;}
}s1, s2;

int n, now = 1;

int a[MAXN], color[MAXN], s[MAXN];

int e[MAXN][MAXN];

bool f = 1;

void in(int x, int c) {
	color[x] = c;
	for (rr int i = 1; i <= n; i++)
		if (e[x][i]) {
			if (color[i] == c) f = 0;
			if (!color[i]) in(i, 3 - c);
		}
}

inline void make() {
	s[n + 1] = inf;
	for (rr int i = n; i >= 1; i--) {
		s[i] = a[i];
		if (s[i + 1] < s[i]) s[i] = s[i + 1];
	}
	for (rr int i = 1; i < n; i++)
		for (rr int j = i + 1; j < n; j++)
			if (a[i] < a[j] && s[j + 1] < a[i])
				e[i][j] = e[j][i] = 1;
	for (rr int i = 1; i <= n; i++) if (!color[i]) in(i, 1);
}

signed main() {
	n = read();
	for (rr int i = 1; i <= n; i++) a[i] = read();
	make();
	if (f == 0) {
		cout << 0;
		return 0;
	}
	for (rr int i = 1; i <= n; i++) {
		if (color[i] == 1) s1.push(a[i]), cout << "a ";
		else s2.push(a[i]), cout << "c ";
		while ((!s1.empty() && s1.top() == now) || (!s2.empty() && s2.top() == now)) 
			if (!s1.empty() && s1.top() == now) s1.pop(), now++, cout << "b ";
			else s2.pop(), now++, cout << "d ";
	}
}