UVa514鐵軌

這道題有兩個(gè)做法。

• 思路一：維護(hù)狀態(tài)掃序列

給每個(gè)序號(hào)維護(hù)一個(gè)狀態(tài)，0表示未進(jìn)入中轉(zhuǎn)站，1表示在中轉(zhuǎn)站中，2表示已出站。遍歷待判斷序列。

對(duì)于當(dāng)前序號(hào)，如果之前已經(jīng)要求它出棧，即狀態(tài)已經(jīng)等于2，而現(xiàn)在才出棧，肯定不對(duì)；如果現(xiàn)在的狀態(tài)等于1，在棧里，可能可以出棧，這就要求比它大的要么出棧了要么沒來；如果現(xiàn)在的狀態(tài)等于0，還未進(jìn)入中轉(zhuǎn)站，就需要它能夠進(jìn)棧，也就是比它小的要么出棧了要么在棧里。

因此，對(duì)編號(hào)大于它的，狀態(tài)只能是0或者2，否則不可能。對(duì)編號(hào)小于它的，只要不是出棧狀態(tài)就一定在棧里，把狀態(tài)給它們刷過去。

出現(xiàn)矛盾的就不可能。

• 思路二：模擬棧直接走

直接比著目標(biāo)序列，看能不能走得出來。

用兩個(gè)指針模擬A和B，A就是1-N的順序序列指針，表示待進(jìn)入中轉(zhuǎn)站的所有列車，B就是目標(biāo)序列的指針，指向當(dāng)前要造的那個(gè)編號(hào)。

注意以哪個(gè)指針作為終止條件。如果以A做條件，不知道當(dāng)前中轉(zhuǎn)站出棧出到什么時(shí)候A才入棧，A指針根本不知道何時(shí)才能往后走，而B指針很明確，能匹配就走，不能匹配就一直停在那兒。

以A做條件明顯復(fù)雜很多，而且很容易出錯(cuò)，復(fù)雜如下：

如果當(dāng)前站臺(tái)(A)上的編號(hào)就是目標(biāo)序列的編號(hào)，那么當(dāng)前編號(hào)的列車直接入中轉(zhuǎn)站再直接出棧，A和B直接都+1。如果當(dāng)前中轉(zhuǎn)站里面的棧頂是，就出棧一直到不能出為止，B+1而A不動(dòng)。如果當(dāng)前中轉(zhuǎn)站里面的棧頂不是，再看站臺(tái)上的，如果當(dāng)前站臺(tái)上的不是目標(biāo)序列的編號(hào)，那么就入棧，興許后續(xù)才出棧，A+1而B不動(dòng)。當(dāng)B移動(dòng)之后，中轉(zhuǎn)站的棧頂又可能滿足了，所以又要判斷一下，這樣其實(shí)就可以無窮無盡下去了。

以B做條件會(huì)簡(jiǎn)單清晰很多，以B來移動(dòng)，如果當(dāng)前車站上的能滿足，就A和B都+1，并讓B往后循環(huán)；如果當(dāng)前中轉(zhuǎn)站的能滿足，就B+1而A不動(dòng)，并讓B往后循環(huán)；如果車站上的和中轉(zhuǎn)站的都不能滿足，車站上的進(jìn)棧，A+1而B不動(dòng)；如果車站上的和中轉(zhuǎn)站的都不滿足而且車站上的已經(jīng)沒有了，break出去，能用的A都用完了。

如果A走完了一遍，目標(biāo)序列還沒有造出來，就不可能。

思路二會(huì)寫棧，思路一不用寫棧。思路二在練習(xí)數(shù)據(jù)結(jié)構(gòu)上更本質(zhì)而且更快。

• 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的tips：

下溢拿來用top = -1。

實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)函數(shù)的時(shí)候就把判空判滿的情況考慮到，比如取棧頂，就在這個(gè)函數(shù)里面判空，如果是空就返回一個(gè)目標(biāo)不可能取到的值。

思路一代碼：

// UVa514鐵軌
// 思路一：掃序列 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int order[MAXN];
int state[MAXN]; // 0表示未進(jìn)入中轉(zhuǎn)站，1表示在棧中，2表示已經(jīng)出棧 
int N;

int main() {
freopen("data.in", "r", stdin);

	while (scanf("%d", &N) == 1 && (N != 0)) {
		int temp = -1;
		while (scanf("%d", &temp) == 1 && (temp != 0)) {
			memset(state, 0, sizeof(state));
			order[1] = temp;
			for (int i = 2; i <= N; i++) {
				scanf("%d", &order[i]);
			}
//			for (int i = 1; i <= N; i++) {
//				printf(" %d", order[i]);
//			}
			int impossible = 0;
			for (int i = 1; i <= N; i++) {
				if (state[order[i]] == 2) { // 如果之前已經(jīng)要求出棧，但是現(xiàn)在才出棧，肯定就不對(duì) 
					impossible = 1;
					break;
				}
				if (state[order[i]] == 1) { // 已經(jīng)是在棧里的，才可能可以出棧，比它大的要么沒來要么在棧里
//					如下有判斷 
				}
				if (state[order[i]] == 0) { // 還沒進(jìn)棧，就必須能進(jìn)棧，比它小的就要么出棧了要么在棧里 
//					如下有判斷 
				}
				for (int k = order[i] + 1; k <= N; k++) { // 編號(hào)比它大的要么沒來要么出棧了 
					if (!(state[k] == 0 || state[k] == 2)) {
						impossible = 1;
						break;
					}
				}
				for (int k = 1; k < order[i]; k++) { // 編號(hào)比它小的要么出棧了要么在棧里 
					if (state[k] != 2) { // 編號(hào)比它小的不是出棧狀態(tài)就一定在棧里 
						state[k] = 1;
					}
					if (!(state[k] == 2 || state[k] == 1)) {
						impossible = 1;
//						printf("???\n");
						break;
					}
				}
				if (impossible == 1) {
					break;
				}
				state[order[i]] = 2; // 標(biāo)記出棧 
			}
			if (impossible == 1) {
				printf("No\n");
			} else {
				printf("Yes\n");
			}
		}
		printf("\n");

	}
	return 0;
} 

思路二代碼：

// UVa514鐵軌
// 思路一：掃序列 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int N;
int stack[MAXN]; 
int order[MAXN];
int top = -1; // 減到空，用來判空 

void Push(int value) {
	top++;
	stack[top] = value;
	return;
}

int Pop() {
	int value = stack[top];
	top--;
	return value;
}

bool isEmpty() {
	if (top == -1) {
		return true;
	} 
	return false;
}

int Top() {
	if (top == -1) { // 當(dāng)前棧為空 
		return -1;
	}
	int value = stack[top];
	return value;
}

int main() {
freopen("data.in", "r", stdin);

	while (scanf("%d", &N) == 1 && (N != 0)) {
		int temp = -1;
		while (scanf("%d", &temp) == 1 && (temp != 0)) {
			int A = 1, B = 1;
			top = -1; // make_empty
			order[1] = temp;
			for (int i = 2; i <= N; i++) {
				scanf("%d", &order[i]);
			}
//			for (int i = 1; i <= N; i++) {
//				printf(" %d", order[i]);
//			}
			while (B <= N) {
				if (A == order[B]) {
					A++;
					B++;
				} else if (Top() == order[B]) {
					Pop();
					B++;
				} else if (A <= N) {
					Push(A);
					A++;
				} else { // A走完了 
					break;
				}
			}
//			printf("%d\n", B);
			if (B != (N + 1)) {
				printf("No\n");
			} else {
				printf("Yes\n");
			}
		}
		printf("\n");

	}
	return 0;
}