计算机程序设计能力考试（PAT）备考通 | PAT模拟样题（提升题）

1.题目名称：One Way In, Two Ways Out（25分）

题目描述

Consider a special queue which is a linear structure that allows insertions at one end, yet deletions at both ends. Your job is to check, for a given insertion sequence, if a deletion sequence is possible. For example, if we insert 1, 2, 3, 4, and 5 in order, then it is possible to obtain 1, 3, 2, 5, and 4 as an output, but impossible to obtain 5, 1, 3, 2, and 4.

输入格式

Each input file contains one test case. For each case, the first line gives 2 positive integers N and K (N,KG10), which are the number of insertions and the number of queries, respectively. Then N distinct numbers are given in the next line, as the insertion sequence. Finally K lines follow, each contains N inserted numbers as the deletion sequence to be checked.

All the numbers in a line are separated by spaces.

输出格式

For each deletion sequence, print in a line“yes”if it is indeed possible to be obtained, or“no”otherwise.

输入样例

输出样例

解题思路

本题是关于一个“一头进、两头出“的队列的问题，即常规队列和堆栈的结合体，考查基本的线性结构的插入和删除操作。

首先，既然明确地知道输入队列的长度，那么选择数组实现这个队列是最合适的。这个队列的初始化和入队操作与普通队列没有区别，只是为了更清楚地表示左右两个端口的操作，可以把传统意义上的队首（ front）和队尾（ rear）指针重新命名为队左（ left）和队右（ right）。真正有区别的是“出队”操作，需要知道用户要求元素从哪一端出队，所以函数接口中要多传递一个表示左右端口的参数。在代码 4.11中， deq函数多了一个 side参数，当传入的值为 1时表示左端出队，队左的指针向右递增；当传入的值为 0时表示右端出队，队右的指针向左递减。

代码 4.11的核心函数是 check(in,out,n)，其中， in是插入序列， out是需要检查的输出序列， n是数据规模。检查的过程就是模拟插入和删除的过程，顺序检查每个 out中的元素，查看其是否有可能从当前的队列中弹出。

具体实现时，分别用两个指针 i和 j指向 out和 in当前的元素，并且先保证队列不是空的——如果队列为空，则先将当前 in[j]插入。对于当前的 out[i]，分别检查当前队列的两端，查看是否有某一端口的元素与其相等——这里只想“看看”队列端口的元素值，并不知道要不要弹出，所以这里单独实现了一个 peek函数，只返回元素，不改变指针（不执行删除操作）。如果某一端的元素值的确与 out[i]相等，则将该元素删除，继续检查下一个 out中的元素。如果两端都不相等，则说明这个元素应该还没有入队，就按 顺序将 in[j]逐一入队，直到发现某个 in[j]的值与 out[i]相等。out序列的错误只可能发生在一个环节，即当应该弹出某个 out[i]时，它早已经在队列中了，却又不在两端。此时如果想得到 out[i]，就必须先弹出其他元素。要想在程序中识别这种情况，只需要在将 in[j]顺序入队时检查 j有没有到达 in的末尾即可。如果全部 in元素都入队了，还没有看到与 out[i]相等的元素，则说明这个 out序列是不可能得到的。

测试要点

除了样例给出的常规测试外，测试数据至少还应考查两种极端情况：所有元素都必须入队后才能开始出队，以及队列中始终只有一个元素。前一种情况对应完全逆序的堆栈操作，后一种情况对应完全顺序的常规队列操作。此外，两端交错出队以及最大和最小规模也应测试到。

源代码 (C) 

■ 代码 4.11 “One Way In, Two Ways Out”源代码

2.题目名称：Distance of Triples（25分）

题目描述

输入格式

输出格式

输入样例

输出样例

解题思路

本题要求从给定的 3个规模为 N₁、N₂、N₃的集合中分别挑出一个元素构成三元组，求所有可能构成的三元组中距离最小的那一个。如果最小距离三元组不唯一，则要求输出最大的那一组解。本题考查的重点是考生对时间复杂度的理解。

最简单的算法是枚举所有可能的三元组并逐一计算距离，从中找出最小值。但这样的算法，其时间复杂度高达 O(N₁×N₂×N₃)，而题目给出的集 合规模的上限高达 10⁴，所以考生应该意识到这种暴力的算法一定会超时。

考虑任何一个三元组 (a,b,c)，不妨假设 a≥b≥c，这个三元组的距离 D(a,b,c)=|a – b|+|b – c|+|c – a|。注意到一个关键点：如果从 a所在的集合中找出一个更大的元素 a'组成新的三元组 (a',b,c)，则因为 a'距离 b和 c更远了，所以这个三元组的距离是不可能变小的。换言之，在计算出 D(a,b,c)之后，是没有必要对任何比 a更大的元素 a'计算 D(a',b,c)的。同理，也没有必要对任何比 c更小的元素 c'计算 D(a,b,c')。这个事实可以帮助考生节省很多计算量。

一个巧妙的算法是：首先将 3个集合中的元素递减排序，然后分别取 3个最大元构成第一个三元组 (a₀,b₀,c₀)，计算这个三元组的距离 D(a₀,b₀,c₀)；然后找出 3个元中的最大值 x₀，将其替换为同集合中的次大元 x₁，以查看新的三元组的距离会不会减小。重复这个步骤，每次找出当前 3个元中的最大值，将其替换为同集合中比它小的下一个元素，如果新的距离变小，就更新当前最小距离。直到 3个集合中有一个集合被扫描到了末尾，整个流程即可结束。这样不仅可以得到最小距离，而且第一次得到最小距离的那个三元组一定是最大的。这样做可以成功的关键在于，把三元组中的最大元变大是肯定不能得到更小距离的，只有将最大元变小，才有可能将距离变小。代码 4.12是对这个算法的实现，其时间复杂度降到了 O(N₁+N₂+N₃)。

当然，还可以换个顺序，将 3个集合中的元素递增排序，每次将最小元变大，也是可以得到解的。但是因为在距离相同的三元组中，题目要求输出最大的那个，这种算法就需要特殊处理这个细节了。例如，给定 3个集合 A={1,4}，B={2,5,6}, C={3,6}，有很多三元组都可以得到最小距离。按照递减排序扫描元素的算法，可以得到第一个三元组 (4,6,6)，其距离为 4，这就是最大解。此后依次检查 (4,5,6)、(4,5,3)、(4,2,3)、(1,2,3)，接下来的最大元 3所在的集合 C已经到了末尾，算法结束。而如果按照递增排序扫描，则第一个三元组是 (1,2,3)，随后每次将最小元变大，依次检查 (4,2,3)、 (4,5,3)、(4,5,6)，这时的最小元 4所在的集合 A已经到了末尾，但 (4,5,6)并不是最大解，虽然其距离的确是最小的 4。

测试要点

样例数据测试了解不唯一的情况，即还存在另外一组解 MinD(9,10,9) =2，但因为 (11,11,12)比较大，所以被输出了。此外，还应该有一组数据专门卡住按递增排序扫描却不能正确得到最大三元组的错误算法。另外，一个集合中的所有元素都大于另一个集合中的所有元素的数据也应该有。当然，最大和最小规模的边界测试也必须有。

源代码 (C) 

■ 代码 4.12 Distance of Triples源代码

计算机程序设计能力考试（PAT）

备考通