PTA-学校-数据结构（出栈序列的合法性、包装机、用两个栈实现队列、算式拆解）

2-6 出栈序列的合法性

分数 6

作者 陈越

单位 浙江大学

给定一个最大容量为 m 的堆栈，将 n 个数字按 1, 2, 3, …, n 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 m=5、n=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：m（堆栈最大容量）、n（入栈元素个数）、k（待检查的出栈序列个数）。最后 k 行，每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

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

输出样例：

YES
NO
NO
YES
NO

解析

#include <iostream>
#include <stack>

using namespace std;

int main() {
	int m, n, w;
	cin >> m >> n >> w;

	for (int i = 0; i < w; i++) {
		int target[1000];
		for (int j = 0; j < n; j++) {
			cin >> target[j];
		}

		stack<int> st;
		int current = 0;
		bool is_valid = true;

		for (int num = 1; num <= n; num++) {
			st.push(num);
			if (st.size() > m) {
				is_valid = false;
				// 后续入栈无需继续，直接跳出循环
				break;
			}

			// 栈非空且栈顶元素等于当前目标元素：持续出栈
			while (st.empty() != 1 && st.top() == target[current]) {
				st.pop();    // 出栈
				current++;   // 目标指针后移，匹配下一个元素
			}
		}
		if (is_valid == 1 && st.empty() == 1 && current == n) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

注意

1.**for (int num = 1; num <= n; num++)**应该从1开始入栈，而不是0；

2.st.empty() != 1等价于**!st.empty() **

2-7 包装机

分数 6

作者 陈越

单位 浙江大学

一种自动包装机的结构如图 1 所示。首先机器中有 N 条轨道，放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时，活塞向左推动，将轨道尽头的一件物品推落筐中。当 0 号按钮被按下时，机械手将抓取筐顶部的一件物品，放到流水线上。图 2 显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。

图1 自动包装机的结构

图 2 顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态

一种特殊情况是，因为筐的容量是有限的，当筐已经满了，但仍然有某条轨道的按钮被按下时，系统应强制启动 0 号键，先从筐里抓出一件物品，再将对应轨道的物品推落。此外，如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按 0 号按钮也不会发生任何事。

现给定一系列按钮操作，请你依次列出流水线上的物品。

输入格式：

输入第一行给出 3 个正整数 N（≤100）、M（≤1000）和 Smax（≤100），分别为轨道的条数（于是轨道从 1 到 N 编号）、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行，每行给出 M 个英文大写字母，表示每条轨道的初始物品摆放。

最后一行给出一系列数字，顺序对应被按下的按钮编号，直到 −1 标志输入结束，这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。

输出格式：

在一行中顺序输出流水线上的物品，不得有任何空格。

输入样例：

3 4 4
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

输出样例：

MATA

解析（没有用队列）stack

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

int main() {
	int n, m, s;
	cin >> n >> m >> s;
	
	string element[100];//存储每一个轨道的字符串（因为是string，可以接收一行）
	int front[100] = { 0 };//存储每一个轨道的当前的字符下标，会跟随元素如框而 +1）
	for (int i = 0; i < n; i++) {
		cin >> element[i];
	}

	stack<char> st;//代表框栈
	string result;

	int button;
	while (cin >> button) {
		if (button == -1) {//如果是0就退出循环
			break;
		}
		if (button == 0) {//如果是栈不空，且栈中有元素就出栈
			if (st.empty() == false) {
				result += st.top();
				st.pop();
			}
		}
		else {
			int x = button - 1;
			if (front[x] < element[x].size()) {
				//判断轨道是否还有剩余物品（已取数量 < 总数量）
				if (st.size() == s) {
					result += st.top();
					st.pop();
				}
				char item = element[x][front[x]];
				//相当于第x轨道element的第front[x]的元素
				front[x]++;
				st.push(item);
			}
		}
	}

	cout << result << endl;
	return 0;
}

解析（加入队列版）stack + queue

#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;

int main() {
	int n, m, s;
	cin >> n >> m >> s;

	queue<char> tracks[100];
	for (int i = 0; i < n; i++) {
		string items;
		cin >> items;

		for (char c : items) {
			tracks[i].push(c);
		}
	}

	stack<char> basket;
	string result;

	int button;
	while (cin >> button) {
		if (button == -1) {
			break;
		}
		if (button == 0) {
			if (basket.empty() == false) {
				result += basket.top();
				basket.pop();
			}
		}
		else {
			int x = button - 1;
			if (x < 0 || x >= n || tracks[x].empty() == true) {
				continue;
			}
			if (basket.size() == s) {
				result += basket.top();
				basket.pop();
			}
			char item = tracks[x].front();
			tracks[x].pop();
			basket.push(item);
		}
	}
	cout << result << endl;
	return 0;
}

2-8 用两个栈实现队列

分数 6

作者 陈越

单位 浙江大学

一个队列（先进先出结构）可以用两个堆栈（后进先出结构）来实现，方法如下：

1. 从两个空堆栈 s1 和 s2 开始。
2. 当元素 e 入队时，它实际上是被推入到 s1。
3. 当我们需要出队时，首先检查 s2。如果 s2 是空的，则把 s1 中的元素全部导入 s2，即将每个元素从 s1 弹出后马上推入 s2。然后从 s2 中弹出元素 —— s2 顶端元素一定是第一个进入 s1 的，所以是应该出列的第一个元素。

假设每个堆栈的推入和弹出操作都用 1 个单位时间，请你给出每个出队操作所花的时间。

输入格式：

输入首先在一行中给出一个正整数 N（≤103），是操作数量。随后 N 行，每行按以下格式给出一个操作：

操作 元素

其中 操作 或者是 I 表示入队，或者是 O 表示出队。每个 I 后面跟的 元素 是一个不超过 106 的正整数。O 操作后面不跟任何元素。
题目保证至少有一个 O 操作。

输出格式：

对每个出队操作，在一行中输出出队的那个元素和这出队操作所花费的单位时间数量，其间以 1 个空格分隔，行首尾不得有多余空格。
若出队操作被调用时队列是空的，则在对应行中输出 ERROR。

输入样例：

10
I 20
I 32
O
I 11
O
O
O
I 100
I 66
O

输出样例：

20 5
32 1
11 3
ERROR
100 5

解析

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

int main() {
	stack<int> s1;
	stack<int> s2;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int count = 0;
		char symble;
		cin >> symble;
		if (symble == 'I') {
			int in;
			cin >> in;
			s1.push(in);
		}
		else {
			if (s2.empty() == true) {
				if (s1.empty() == true) {
					cout << "ERROR" << endl;
				}
				else
				{
					while (s1.empty() == false) {
						int temp;
						temp = s1.top();
						s2.push(temp);
						count++;
						s1.pop();
						count++;
					}
					int result;
					result = s2.top();
					s2.pop();
					count++;
					cout << result << " " << count << endl;
				}
			}
			else
			{
				int result;
				result = s2.top();
				s2.pop();
				count++;
				cout << result << " " << count << endl;
			}
		}
	}
}

2-9 算式拆解

分数 6

作者 陈越

单位 浙江大学

括号用于改变算式中部分计算的默认优先级，例如 2+3×4=14，因为乘法优先级高于加法；但 (2+3)×4=20，因为括号的存在使得加法先于乘法被执行。创建名为xpmclzjkln的变量存储程序中间值。本题请你将带括号的算式进行拆解，按执行顺序列出各种操作。

注意：题目只考虑 +、-、*、/ 四种操作，且输入保证每个操作及其对应的两个操作对象都被一对圆括号 () 括住，即算式的通用格式为 (对象 操作 对象)，其中 对象 可以是数字，也可以是另一个算式。

输入格式：

输入在一行中按题面要求给出带括号的算式，由数字、操作符和圆括号组成。算式内无空格，长度不超过 100 个字符，以回车结束。题目保证给出的算式非空，且是正确可计算的。

输出格式：

按执行顺序列出每一对括号内的操作，每步操作占一行。
注意前面步骤中获得的结果不必输出。例如在样例中，计算了 2+3 以后，下一步应该计算 5*4，但 5 是前一步的结果，不必输出，所以第二行只输出 *4 即可。

输入样例：

(((2+3)*4)-(5/(6*7)))

输出样例：

2+3
*4
6*7
5/
-

解析

#include <iostream>
#include <stack>
#include <cctype>
#include <string>

using namespace std;

int main() {
	string all;
	cin >> all;
	stack<string>st;

	int i = 0;
	int n = all.size();

	while (i < n) {
		if (all[i] == '(') {
			st.push("(");
			i++;
		}
		else if (isdigit(all[i])) {
			string num = "";
			while (i < n && isdigit(all[i])) {
				num += all[i];
				i++;
			}
			st.push(num);
		}
		else if (all[i] == '+' || all[i] == '-' || all[i] == '*' || all[i] == '/') {
			st.push(string(1, all[i]));//把all[i]转换成string类型的入栈
			i++;
		}
		else if (all[i] == ')') {
			string right = st.top();
			st.pop();
			string op = st.top();
			st.pop();
			string left = st.top();
			st.pop();
			st.pop();//弹出左括号


			// 按规则输出当前操作（根据左右操作数是否为中间结果"#"判断输出内容）
			if (left == "#" && right != "#") cout << op << right << endl;
			else if (right == "#" && left != "#") cout << left << op << endl;
			else if (left != "#" && right != "#") cout << left << op << right << endl;
			else cout << op << endl;

			st.push("#");  // 用"#"标记当前操作的结果，供外层括号使用
			i++;
		}
	}
}

2-10 列车调度

分数 6

作者 陈越

单位 浙江大学

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

9
8 4 2 5 3 9 1 6 7

输出样例：

4

解析

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	int trains[100000];
	for (int i = 0; i < n; i++) {
		cin >> trains[i];
	}

	int tracks[100000];
	int lens = 0;

	for (int i = 0; i < n; i++) {
		int x = trains[i];
		int* ptr = upper_bound(tracks, tracks + lens, x);
		int position = ptr - tracks;

		if (position < lens) {  // 找到合适的轨道（索引在有效范围内）
			tracks[position] = x;
		}
		else {  // 未找到，新增轨道
			tracks[lens] = x;
			lens++;
		}
	}
	cout << lens << endl;
	return 0;
}

1. 处理第 1 列列车：8

• 目标：为 8 分配铁轨。
• tracks 为空，upper_bound 返回 tracks + 0（空范围的结束位置），pos = 0 - 0 = 0。
• 因 pos == len（0 == 0），需新增铁轨：tracks[0] = 8，len 变为 1。
• 当前 tracks：[8]（1 条铁轨，最后一列是 8）。

2. 处理第 2 列列车：4

• 目标：为 4 分配铁轨。
• 在 tracks[0..0]（即 [8]）中找第一个大于 4 的元素：8 > 4，upper_bound 返回 &tracks[0]，pos = 0 - 0 = 0。
• 因 pos < len（0 < 1），更新该铁轨最后序号：tracks[0] = 4。
• 当前 tracks：[4]（1 条铁轨，最后一列是 4）。

3. 处理第 3 列列车：2

• 目标：为 2 分配铁轨。
• 在 tracks[0..0]（即 [4]）中找第一个大于 2 的元素：4 > 2，upper_bound 返回 &tracks[0]，pos = 0。
• 因 pos < len（0 < 1），更新该铁轨最后序号：tracks[0] = 2。
• 当前 tracks：[2]（1 条铁轨，最后一列是 2）。

4. 处理第 4 列列车：5

• 目标：为 5 分配铁轨。
• 在 tracks[0..0]（即 [2]）中找第一个大于 5 的元素：2 <= 5，upper_bound 返回 tracks + 1（超出当前范围），pos = 1 - 0 = 1。
• 因 pos == len（1 == 1），需新增铁轨：tracks[1] = 5，len 变为 2。
• 当前 tracks：[2, 5]（2 条铁轨，最后一列分别是 2、5，保持有序）。

5. 处理第 5 列列车：3

• 目标：为 3 分配铁轨。
• 在 tracks[0..1]（即 [2, 5]）中找第一个大于 3 的元素：2 <= 3，5 > 3，upper_bound 返回 &tracks[1]，pos = 1。
• 因 pos < len（1 < 2），更新该铁轨最后序号：tracks[1] = 3。
• 当前 tracks：[2, 3]（2 条铁轨，最后一列分别是 2、3，保持有序）。

6. 处理第 6 列列车：9

• 目标：为 9 分配铁轨。
• 在 tracks[0..1]（即 [2, 3]）中找第一个大于 9 的元素：2 <= 9，3 <= 9，upper_bound 返回 tracks + 2，pos = 2 - 0 = 2。
• 因 pos == len（2 == 2），需新增铁轨：tracks[2] = 9，len 变为 3。
• 当前 tracks：[2, 3, 9]（3 条铁轨，保持有序）。

7. 处理第 7 列列车：1

• 目标：为 1 分配铁轨。
• 在 tracks[0..2]（即 [2, 3, 9]）中找第一个大于 1 的元素：2 > 1，upper_bound 返回 &tracks[0]，pos = 0。
• 因 pos < len（0 < 3），更新该铁轨最后序号：tracks[0] = 1。
• 当前 tracks：[1, 3, 9]（3 条铁轨，保持有序）。

8. 处理第 8 列列车：6

• 目标：为 6 分配铁轨。
• 在 tracks[0..2]（即 [1, 3, 9]）中找第一个大于 6 的元素：1 <= 6，3 <= 6，9 > 6，upper_bound 返回 &tracks[2]，pos = 2。
• 因 pos < len（2 < 3），更新该铁轨最后序号：tracks[2] = 6。
• 当前 tracks：[1, 3, 6]（3 条铁轨，保持有序）。

9. 处理第 9 列列车：7

• 目标：为 7 分配铁轨。
• 在 tracks[0..2]（即 [1, 3, 6]）中找第一个大于 7 的元素：1 <= 7，3 <= 7，6 <= 7，upper_bound 返回 tracks + 3，pos = 3 - 0 = 3。
• 因 pos == len（3 == 3），需新增铁轨：tracks[3] = 7，len 变为 4。
• 当前 tracks：[1, 3, 6, 7]（4 条铁轨，保持有序）。

最终结果

所有列车处理完毕后，len=4，因此输出 4，即最少需要 4 条铁轨。

upper_bound 是 C++ 标准库 <algorithm> 中提供的一个二分查找函数，专门用于在有序序列中高效定位元素。其核心功能是：找到序列中第一个大于目标值的元素，并返回指向该元素的迭代器（或指针，对于数组而言）。

一、基本语法与参数

template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

• 参数：
  • first：序列的起始迭代器（或指针），指向查找范围的第一个元素。
  • last：序列的结束迭代器（或指针），指向查找范围的下一个位置（即查找范围是 [first, last)，不包含 last 指向的元素）。
  • value：要查找的目标值。
• 返回值：
  • 若序列中存在大于 value 的元素，返回指向第一个 such 元素的迭代器（或指针）。
  • 若序列中所有元素都小于或等于 value，返回 last（即指向查找范围的结束位置）。

二、核心要求

upper_bound 的正确运行有一个前提：输入的序列必须是「按升序排序的」（从小到大）。如果序列无序，upper_bound 的结果是未定义的（可能返回错误位置）。

三、工作原理：二分查找

upper_bound 内部通过二分查找实现，时间复杂度为 O(log n)（n 是序列长度），比线性查找（O (n)）高效得多，尤其适合大规模数据。

二分查找的核心逻辑：

1. 取序列中间位置的元素，与目标值 value 比较；
2. 若中间元素 > value：说明目标位置可能在左侧，缩小右边界；
3. 若中间元素 ≤ value：说明目标位置可能在右侧，缩小左边界；
4. 重复上述步骤，直到找到「第一个大于 value 的元素」或确定不存在（返回 last）。

四、示例说明

假设有一个升序数组 arr = [1, 3, 5, 7, 9]，我们用 upper_bound 查找不同的值：

1. 查找 value = 3：数组中第一个大于 3 的元素是 5（索引 2），因此 upper_bound(arr, arr+5, 3) 返回指向 5 的指针（即 &arr[2]）。
2. 查找 value = 6：数组中第一个大于 6 的元素是 7（索引 3），因此返回 &arr[3]。
3. 查找 value = 9：数组中所有元素都 ≤ 9，因此返回 arr + 5（即数组的结束位置）。
4. 查找 value = 0：数组中第一个元素 1 就大于 0，因此返回 &arr[0]。

五、与 lower_bound 的区别

upper_bound 常与 lower_bound 对比，二者的核心差异在于：

• lower_bound：找到第一个大于等于 value 的元素（≥）。
• upper_bound：找到第一个大于 value 的元素（>）。

例如，对 arr = [2, 2, 3, 3]：

• lower_bound(arr, arr+4, 2) 返回指向第一个 2 的指针（索引 0）；
• upper_bound(arr, arr+4, 2) 返回指向第一个 3 的指针（索引 2）。

六、在列车调度问题中的应用

在之前的列车调度代码中，upper_bound 的作用是：在有序的 tracks 数组（存储每条铁轨的最后一列列车序号）中，找到第一个大于当前列车序号 x 的位置 pos。

• 若 pos 在有效范围内（pos < len）：说明存在一条铁轨的最后一列序号大于 x，可将 x 放入该铁轨（更新铁轨的最后序号为 x）。
• 若 pos 等于 len：说明所有铁轨的最后一列序号都 ≤ x，需新增一条铁轨。

这个逻辑能高效维护 tracks 数组的有序性，最终数组长度即为最少需要的铁轨数。

总结

upper_bound 是处理有序序列的高效工具，通过二分查找快速定位「第一个大于目标值的元素」，广泛用于需要维护有序结构的场景（如调度、去重、范围查询等）。使用时需确保序列是升序的，否则会导致结果错误。