【PAT甲级 - C++题解】1051 Pop Sequence

简介: 【PAT甲级 - C++题解】1051 Pop Sequence

1051 Pop Sequence


Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.


Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.


Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.


Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO


题意

给定一个最多能存 M 个数字的栈,将 1∼N 按顺序压入栈中,过程中可随机弹出栈顶元素。


当 N 个数字都经历过入栈和出栈后,我们按照元素出栈的顺序,可以得到一个弹出序列。


现在给定一系列 1∼N 的随机排列序列,请你判断哪些序列可能是该栈的弹出序列。


例如,当 N=7,M=5 时,1, 2, 3, 4, 5, 6, 7可能是该栈的弹出序列,而 3, 2, 1, 7, 5, 6, 4 不可能是该栈的弹出序列。


思路

这题是一道栈模拟的题目,每次模拟操作只有两个选择:


1.推入元素,即如果当前栈顶元素不等于当前需要输出的元素,则推入新的元素。

2.弹出元素,即如果当前栈顶元素等于当前需要输出的元素,则弹出栈顶元素,直至不相等为止。


而判断该弹出序列是否满足要求同样有两个依据:


1.栈中元素不能大于 m 。

2.做完所有操作后,栈中不能有元素即所有栈顶元。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int m, n, k;
bool check()
{
    stack<int> stk;
    for (int i = 1, j = 0; i <= n; i++)
    {
        stk.push(i);
        //已经超出栈的容量,则返回false
        if (stk.size() > m)    return false;
        //判断当前输出的元素是否与栈顶元素相等
        while (stk.size() && stk.top() == a[j])
        {
            stk.pop();
            j++;
        }
    }
    return stk.empty();
}
int main()
{
    cin >> m >> n >> k;
    while (k--)
    {
        for (int i = 0; i < n; i++)    cin >> a[i];
        if (check()) puts("YES");
        else    puts("NO");
    }
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
67 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
85 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
79 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
78 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
79 0
|
人工智能 BI C++
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
【PAT甲级 - C++题解】1148 Werewolf - Simple Version
138 0
|
14天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
25 2
|
20天前
|
存储 编译器 C++
【c++】类和对象(下)(取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象)
本文介绍了C++中类和对象的高级特性,包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项,帮助读者深入了解C++面向对象编程的核心机制。
54 5
|
26天前
|
存储 编译器 C++
【c++】类和对象(中)(构造函数、析构函数、拷贝构造、赋值重载)
本文深入探讨了C++类的默认成员函数,包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化,析构函数用于对象销毁时的资源清理,拷贝构造函数用于对象的拷贝,赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项,并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
56 4
|
27天前
|
存储 编译器 Linux
【c++】类和对象(上)(类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针)
本文介绍了C++中的类和对象,包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用,以及如何使用访问限定符控制成员的访问权限。此外,还讨论了对象的内存分配规则和this指针的使用场景,帮助读者深入理解面向对象编程的核心概念。
65 4