UVA 514 Rails

Stack好题

题目

题目大意

火车车厢从1-n，可以从一个轨道进，从另一个轨道出，后进先出。给定一个新的排列，判断是否可以通过两条铁轨，形成这个新的排列。

题解

用栈模拟火车进出过程即可，满足新队列就可出栈，若出栈数目等于火车车厢数则可以排成新队列。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int maxn = 1000 + 5;
int a[maxn];
int main()
{
        int n, i, k;
        while (scanf("%d", &n) && n)
        {
                stack<int>s;
                while (scanf("%d", &a[0]) && a[0])
                {
                        for (i = 1; i < n; i++)
                        {
                                scanf("%d", &a[i]);
                        }
                        for (i = 1, k = 0; i <= n; i++)
                        {
                                s.push(i);
                                while (s.top() == a[k])
                                {
                                        if (!s.empty())
                                        {
                                                s.pop();
                                        }
                                        k++;
                                        if (s.empty())
                                        {
                                                break;
                                        }
                                }
                        }
                        if (k == n)
                        {
                                printf("Yes\n");
                        }
                        else
                        {
                                printf("No\n");
                        }
                }
                printf("\n");
        }
        return 0;
}