xxyQwQ
0%

【题解】ACMOJ 14151 出栈序列

发表于 分类于

题目描述

ACMOJ - 14151 - 出栈序列

现有 $n$ 个整数 $1,2,\dots ,n$ 依次入栈，判断出栈序列的合法性

题目存在 $T$ 组测试数据，每组数据规模为 $n$，保证 $T\leq 10,n\leq 10^6$

问题分析

事实上，我们直接对出入栈操作进行模拟即可

按照出栈顺序遍历每一个整数 $a_i$，若其未曾入栈，将所有不大于 $a_i$ 的整数依次入栈，并将 $a_i$ 弹出，若其已在栈中，倘若其在栈顶，弹出即可，否则断言该出栈序列不合法

该算法的时间复杂度为 $O(T\cdot n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <cstring>
const int NMAX = 1000005;

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

int stack[NMAX], top, current, a[NMAX], T, n;

int main()
{
    read(T);
    while (T--)
    {
        bool fail = false;
        top = 0, current = 0;
        read(n);
        for (int i = 1; i <= n; i++)
            read(a[i]);
        for (int i = 1; i <= n; i++)
        {
            if (a[i] <= current && stack[top] != a[i])
            {
                fail = true;
                break;
            }
            if (stack[top] == a[i])
            {
                top--;
                continue;
            }
            while (current < a[i])
            {
                current++;
                stack[++top] = current;
            }
            top--;
        }
        printf("%s\n", fail ? "No" : "Yes");
    }
    return 0;
}