A29396. 两头进一头出
填空题
困难
知识点
题目描述
两头进一头出
题目描述
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。现给定入队的序列，请你判断一系列出队序列是否可能。例如按 1、2、3、4、5 的顺序入队，则 1、3、2、5、4 这样的出队序列是可以得到的，但 5、1、3、2、4 就是不可能得到的。
输入
输入首先在一行中给出两个正整数 N 和 K（≤ 10），分别是入队元素的个数和待查验的序列个数。随后一行给出 N 个两两不同的整数组成的入队序列；再跟着 K 行，每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。
输出
对每个需要查验的出队序列，如果是可能的，则在一行中输出 `yes`，否则输出 `no`。
样例输入
5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2样例输出
yes
no
yes
no参考答案
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
// 回溯函数：尝试插入/弹出操作，验证是否匹配出队序列
bool backtrack(deque<int>& dq, const vector<int>& in, const vector<int>& out, int i, int j, int N) {
// 所有出队元素匹配完成，返回成功
if (j == N) {
return true;
}
// 尝试弹出队头（若匹配当前出队元素）
if (!dq.empty() && dq.front() == out[j]) {
int val = dq.front();
dq.pop_front();
// 递归检查后续匹配
if (backtrack(dq, in, out, i, j + 1, N)) {
return true;
}
// 回溯：恢复弹出的元素
dq.push_front(val);
}
// 尝试插入下一个入队元素（若还有未插入的元素）
if (i < N) {
// 插入队头
dq.push_front(in[i]);
if (backtrack(dq, in, out, i + 1, j, N)) {
return true;
}
// 回溯：撤销队头插入
dq.pop_front();
// 插入队尾
dq.push_back(in[i]);
if (backtrack(dq, in, out, i + 1, j, N)) {
return true;
}
// 回溯：撤销队尾插入
dq.pop_back();
}
// 无可行操作，返回失败
return false;
}
int main() {
int N, K;
cin >> N >> K;
// 读取入队序列
vector<int> in(N);
for (int i = 0; i < N; ++i) {
cin >> in[i];
}
// 处理K个待查验的出队序列
while (K--) {
vector<int> out(N);
for (int i = 0; i < N; ++i) {
cin >> out[i];
}
deque<int> dq; // 模拟双端队列
bool is_valid = backtrack(dq, in, out, 0, 0, N);
cout << (is_valid ? "yes" : "no") << endl;
}
return 0;
}
上一题
下一题