[栈思想]uva-514-Rails

发布于 2019-07-23  400 次阅读


https://cn.vjudge.net/problem/UVA-514

uva好像有点卡 上了vj地址

看起来就是用栈 其实也不是很好想
简单说下思路 进栈顺序为A 1 2 3 4 5
出栈顺序给了B 同时有一个栈C 同时处理这几个部分
1.目的是B读取完毕 如果读不完 那么就出问题了 就是这个出栈序列是有问题的
2.如果A的数字和B的相同 那么直接省略这个车 A++ B++ 处理下一辆车
3.如果栈不空 且栈顶元素 和arr[B]相同 那么出栈 B++
4.如果A没有走完 A入栈 且A++
5.如果完不成234 那么就是失败了


越努力越幸运。

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int arr[maxn];

int main() {
	int n, A, B, flag;//A代表车厢序号(1 2 3 4 5 6) B代表已经驶出B的车辆数
	while (scanf("%d", &n), n) {
		stack<int>s;
		while (1) {
			scanf("%d", &arr[1]);
			if (arr[1] == 0) break;
			for (int i = 2; i <= n; i++) {
				scanf("%d", &arr[i]);
			}
			A = B = flag = 1;
			while (B <= n)//未全驶出
			{
				if (A == arr[B]) {//进栈的车和驶向B的车相同
					A++;
					B++;
				}
				else if (!s.empty() && s.top() == arr[B]) {//栈顶和要出栈的相同
					s.pop();
					B++;
				}
				else if (A <= n) {
					s.push(A);
					A++;
				}
				else {
					flag = 0;
					break;
				}
			}
			printf("%s\n", flag ? "Yes" : "No");
		}
		printf("\n");
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。