There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.

The last block consists of just one line containing 0.

题解：火车进站问题（栈混洗验证）

一、问题本质

本题是经典的栈混洗问题：给定一个死胡同车站（栈结构），判断是否能通过入栈/出栈操作，将顺序到达的车厢（1, 2, ..., N）重排为目标序列。核心在于模拟物理调度过程，验证序列可行性。

二、解题思路

    • 车站 = 栈（后进先出）
    • A方向 → 车站：压栈操作
    • 车站 → B方向：弹栈操作
    • 车厢编号1~N必须按顺序到达
    • 按顺序将车厢1→N压入栈
    • 每次压栈后，立即检查栈顶是否匹配目标序列
    • 若匹配则弹出栈顶，并推进目标序列指针
    • 重复直到不匹配或栈空
    • 当所有车厢处理完毕后：
      • 栈为空 → 所有车厢按目标序列出栈 → 可行
      • 栈非空 → 有车厢阻塞无法出栈 → 不可行

三、代码实现

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n && n != 0) {  // 全局结束条件
        while (true) {
            vector<int> target(n + 1); // 1-based索引存储目标序列
            cin >> target[1];
            if (target[1] == 0) break; // 块结束标记

            // 读取完整目标序列
            for (int i = 2; i <= n; ++i) {
                cin >> target[i];
            }

            stack<int> station; // 模拟车站
            int next_target = 1; // 目标序列当前位置指针

            // 模拟1~N车厢依次进站
            for (int coach = 1; coach <= n; ++coach) {
                station.push(coach); // 当前车厢进站
                
                // 贪心匹配：栈顶匹配目标序列时立即出站（这个while是重点，需要特别注意）
                while (!station.empty() && station.top() == target[next_target]) {
                    station.pop();
                    next_target++; // 推进目标指针
                }
            }
            
            // 结果判定：栈空表示所有车厢按序出站
            if (station.empty()) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
        cout << endl; // 块结束分隔符（注意：原题未要求，但代码保留）
    }
    return 0;
}

四、 结果判定等价性：

  • station.empty() ⇔ next_target == n+1
  • 两者等价，因每次匹配成功同时满足：
    • 弹出一个车厢
    • 推进一个目标位置

五、复杂度分析

项目 说明
时间复杂度 O(N)（每个车厢最多入栈/出栈1次）
空间复杂度 O(N)（栈和目标序列存储）
最大N 1000（栈深度安全）

六、典型错误规避

  1. 状态未重置：

    • 错误：在块循环外声明栈
    • 修正：每次序列测试前重新初始化栈（代码中stack<int> station在内层循环内声明）

  2. 指针越界：（需要特别注意）

    • 错误：while(station.top() == target[next_target])未检查栈空
    • 修正：while(!station.empty() && ...)