C++算法题解：死胡同汽车倒车问题

问题描述

假设有一个只能容纳一辆汽车通过的死胡同，多辆汽车先后进入死胡同，导致最先进入的汽车最后才能倒出。给定汽车进入死胡同的顺序和一个预期的倒车顺序，判断汽车是否能够按照预期的顺序全部倒出。

输入格式

首先输入一个整数 T，表示测试数据的组数。* 然后是 T 组测试数据。* 每组测试数据首先输入一个正整数 n（n≤10），代表进入死胡同的汽车数量。* 然后输入 2n 个整数，其中前 n 个整数表示汽车进入死胡同的顺序，后 n 个整数表示汽车预期的倒车顺序。

输出格式

对于每组测试数据，判断汽车能否按照预期顺序倒出死胡同。* 若能，则输出 'Yes'，否则输出 'No'。（输出不包含引号）

C++代码实现cpp#include #include #include using namespace std;

bool canExit(int n, vector& carArrival, vector& carExit) { stack st; int arrivalIdx = 0, exitIdx = 0;

while (exitIdx < n) {        if (!st.empty() && st.top() == carExit[exitIdx]) {            st.pop();            exitIdx++;        } else if (arrivalIdx < n) {            st.push(carArrival[arrivalIdx]);            arrivalIdx++;        } else {            return false;        }    }

return true;}

int main() { int T; cin >> T;

while (T--) {        int n;        cin >> n;

    vector<int> carArrival(n);        vector<int> carExit(n);

    for (int i = 0; i < n; i++) {            cin >> carArrival[i];        }

    for (int i = 0; i < n; i++) {            cin >> carExit[i];        }

    if (canExit(n, carArrival, carExit)) {            cout << 'Yes' << endl;        } else {            cout << 'No' << endl;        }    }

return 0;}

代码解释

canExit 函数： - 使用栈 st 模拟死胡同，后进先出。 - arrivalIdx 和 exitIdx 分别表示进入序列和倒车序列的当前索引。 - 遍历倒车序列 carExit： - 若栈顶元素等于当前需倒出的汽车，则弹出栈顶元素，exitIdx 加 1。 - 否则，若还有未进入死胡同的汽车，则将下一辆汽车入栈，arrivalIdx 加 1。 - 若以上条件均不满足，则无法按照预期顺序倒车，返回 false。 - 遍历结束后，若栈为空，则表示所有汽车已成功倒出，返回 true。
main 函数： - 读取测试数据组数 T。 - 循环处理每组测试数据： - 读取汽车数量 n，进入序列 carArrival 和倒车序列 carExit。 - 调用 canExit 函数判断能否按照预期顺序倒车，并输出结果。

总结

本题利用栈模拟死胡同的后进先出特性，巧妙地解决了汽车倒车问题。通过分析进入和倒车顺序，可以判断汽车是否能够顺利倒出。