鑽石舞台

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個規模為 N1、N2、N3的集合中分別挑出一個元素構成三元組，求所有可能構成的三元組中距離最小的那一個。如果最小距離三元組不唯一，則要求輸出最大的那一組解。本題考查的重點是考生對時間複雜度的理解。

最簡單的算法是枚舉所有可能的三元組並逐一計算距離，從中找出最小值。但這樣的算法，其時間複雜度高達 O(N1×N2×N3)，而題目給出的集 合規模的上限高達 104，所以考生應該意識到這種暴力的算法一定會超時。

考慮任何一個三元組 (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個最大元構成第一個三元組 (a0,b0,c0)，計算這個三元組的距離 D(a0,b0,c0)；然後找出 3個元中的最大值 x0，將其替換為同集合中的次大元 x1，以查看新的三元組的距離會不會減小。重複這個步驟，每次找出當前 3個元中的最大值，將其替換為同集合中比它小的下一個元素，如果新的距離變小，就更新當前最小距離。直到 3個集合中有一個集合被掃描到了末尾，整個流程即可結束。這樣不僅可以得到最小距離，而且第一次得到最小距離的那個三元組一定是最大的。這樣做可以成功的關鍵在於，把三元組中的最大元變大是肯定不能得到更小距離的，只有將最大元變小，才有可能將距離變小。代碼 4.12是對這個算法的實現，其時間複雜度降到了 O(N1+N2+N3)。

當然，還可以換個順序，將 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）

備考通