Rail_UVa514_栈

迈不过友情╰ 2022-01-05 14:55 144阅读 0赞

1 /*
     2     https://vjudge.net/problem/UVA-514
     3 */
     4 #include "pch.h"
     5 #include<iostream>
     6 #include<cstdio>
     7 #include<stack>
     8 using namespace std;
     9 const int MAXN = 1000 + 10;
    10 int n, target[MAXN];
    11 
    12 int main()
    13 {
    14     
    15     while (scanf("%d", &n) == 1) // 输入，一共n辆火车
    16     {
    17         int isOnePart = 1; // 是否是同一次测试
    18         if (n == 0) // 程序应当结束
    19             break;
    20         while (isOnePart) // 是同一次测试时
    21         {
    22             stack<int> s;
    23             int A = 1, B = 1; // A:进C站顺序 1,2,3,...,n   B:数组target的下标
    24             for (int i = 1; i <= n; i++)
    25             {
    26                 scanf("%d", &target[i]); // 输入出C站顺序
    27                 if (target[i] == 0)
    28                 {
    29                     isOnePart = 0;
    30                     printf("\n"); // 注意！
    31                     break;
    32                 }
    33             }
    34             if (isOnePart == 0) // 退出此次测试，进入另一部分的测试
    35                 break;
    36             int ok = 1;   // 标志，是否可以按顺序出站
    37             while (B <= n) // 判断当前出C站的车辆数是否达到总数
    38             {
    39                 if (A == target[B]) // 要进站的火车与要出站的火车为同一辆，则进站后直接出站
    40                 {
    41                     A++; B++;
    42                 }
    43                 else if (!s.empty() && s.top() == target[B])  // 栈（站）非空，栈顶与要出站的火车相同，则出站
    44                 {
    45                     s.pop();
    46                     B++;  // 要出站的++
    47                 }
    48                 else if (A <= n)  // 要进站的与出站的不同，只进站，先等着，当栈顶与目标相同时再出（上一个if）
    49                 {
    50                     s.push(A++);
    51                 }
    52                 else
    53                 {
    54                     ok = 0;  //正常结束循环为b=n,  若前几种情况都不符合，则不能按照要求顺序出站，break
    55                     break;
    56                 }
    57             }
    58             printf("%s\n", ok ? "Yes" : "No");
    59         }
    60         
    61     }
    62     return 0;
    63 }

转载于:https://www.cnblogs.com/tornado549/p/10411201.html