页面加载中…
P5102. 火车迷
简单通过率 74% · 提交 34 · 通过 25
美团栈模拟贪心
华为 OD 机考真题方向改编 · 聚焦「美团 / 栈」 · 难度：简单
小慕最近迷上了火车调度。他在观察家附近的一个火车站时，发现火车驶入和驶出的顺序并不总是一致的。 经过小慕调查，原来这个火车站里有一个类似于的结构，如下图所示： 例如，可能1号火车先驶入了火车站中的休息区s，在它驶出之前，2号火车又驶入了。 在这种情况下，1号火车必须等待2号火车先倒车出去后才能离开（因为被后面驶入的2号火车挡住了，而这个休息区s只有一个出入口）。 出于好奇，小慕统计了近些天的火车驶入驶出情况，开始统计和结束统计时，休息区s中都是空的。 由于中途疏忽，小慕觉得自己可能弄错了几个驶入驶出的顺序，想请你帮他验证一下。 值得注意的是，小慕虽然可能弄错了顺序，但对火车的记录是的。 形式化地描述休息区s，我们将其视为一个容量无限大的空间。假设两列火车 i 和 j 同时处于休息区s中，驶入时刻Tin满足Tin(i) Tout(j)，即先进后出。
这类题属于华为 OD 机考真题方向中「美团 / 栈」方向的高频题型，通常考察对「美团 / 栈」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入一个整数T表示数据组数。
对每组测试而言：
第一行输入一个整数n，表示观察到的火车数量。
第二行输入n个整数x1,x2,...,xn，表示小美记录的火车驶入休息区s的顺序。
第三行输入n个整数y1,y2,...,yn，表示小美记录的火车驶出休息区s的顺序。
1 ≤ T ≤ 10，1 ≤ n ≤ 50000，1 ≤ xi, yi ≤n， 且{xn} 、{yn} 均为{1,2,3,...,n}的一个排列，即1~n这n个数在其中不重不漏恰好出现一次。
输出描述
对每组数据输出一行：如果小美记录的驶入和驶出顺序无法被满足则输出No，否则输出Yes。
示例
示例 1
输入示例
3 3 1 2 3 1 2 3 3 1 2 3 3 2 1 3 1 2 3 3 1 2
输出示例
Yes Yes No
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
