2.3　C++與STL入門

本節選解習題來源于《算法競賽入門經典（第2版）》一書的第5章。

本章的習題主要是為了練習C++語言以及STL，程序本身并不一定很復雜。建議讀者至少完成8道習題。如果想達到更好的效果，建議完成12題或以上。

習題5-1　代碼對齊（Alignment of Code, ACM/ICPC NEERC 2010, UVa1593）

輸入若干行代碼，要求各列單詞的左邊界對齊且盡量靠左。單詞之間至少要空一格。每個單詞不超過80個字符，每行不超過180個字符，一共最多1000行，如圖2.17所示。

【分析】

可以將所有的單詞看作一個表格，則每一行被空格串切分成多個列。每一列的寬度就是表格中當前列的最長單詞的寬度。輸出時，列與列之間用一個空格分開。

建議使用STL的I/O流，讀一行使用getline(cin,line)，其中line是string。對line的切分，可以使用stringstream。切分過程中，更新每一列單詞的最大長度。輸出時可用setw來設置一個輸出對象的寬度。具體可以查詢STL使用手冊。完整程序如下：

習題5-2　Ducci序列（Ducci Sequence, ACM/ICPC Seoul 2009, UVa1594）

對于一個n元組(a₁,a₂,…,a_n)，可以對每個數求出它和下一個數的差的絕對值，得到一個新的n元組(|a₁-a₂|,|a₂-a₃|,…,|a_n-a₁|)。重復這個過程，得到的序列稱為Ducci序列，例如：

(8, 11, 2, 7) → (3, 9, 5, 1) → (6, 4, 4, 2) → (2, 0, 2, 4) → (2, 2, 2, 2) → (0, 0, 0, 0)

也有的Ducci序列會一直循環。輸入n元組（3≤n≤15），你的任務是判斷它最終會變成0還是會一直循環。輸入保證最多1000步就會變成0或者循環。

【分析】

序列可以直接使用vector<int>模擬，vector本身已經重載了等號運算符對兩個容器的內容進行比較。所以判重和判是否全0直接用“==”操作符即可，判重可以使用set < vector<int> >。完整程序如下：

習題5-3　卡片游戲（Throwing cards away I, UVa10935）

桌上有n（n≤50）張牌，從第一張牌（即位于頂面的牌）開始從上往下依次編號為1～n。當至少還剩兩張牌時進行以下操作：把第一張牌扔掉，然后把新的第一張放到整疊牌的最后。輸入每行包含一個n，輸出每次扔掉的牌，以及最后剩下的牌。

【分析】

因為對牌堆的操作就是出隊和入隊，直接使用STL里面的queue來模擬牌堆即可。需要注意的特殊情況是，當n=1時，直接輸出“Discarded cards:”，行尾是不包含空格的。完整程序如下：

習題5-4　交換學生（Foreign Exchange, UVa10763）

有n（1≤n≤500000）個學生想交換到其他學校學習。為了簡單起見，規定每個想從A學校換到B學校的學生必須找一個想從B換到A的“搭檔”。如果每個人都能找到自己的搭檔（一個人不能當多個人的搭檔），學校就會同意他們交換。每個學生用兩個整數A、B表示，你的任務是判斷交換是否可以進行。

【分析】

對于每所學校，如果要交換成功，必須要出去和要進來的人數完全相等。可以在輸入的同時記每一個A和B組成的整數對，以及對應的A→B的交換學生個數。

輸入完成后，遍歷所有的（A,B），看看對應的學生個數是否和（B,A）的相同，若有不同，則交換不能進行。完整程序（C++11）如下：

習題5-5　復合詞（Compound Words，UVa 10391）

給一個詞典，找出所有的復合詞，即恰好有兩個單詞連接而成的單詞。輸入每行都是一個由小寫字母組成的單詞。輸入已按照字典序從小到大排序，且不超過120 000個單詞。輸出所有復合詞，按照字典序從小到大排列。

【分析】

使用set＜string＞來存儲所有單詞，然后對每個單詞的所有左右切分方案進行遍歷，判斷切分出來的兩個子字符串兩邊是否同時存在于set中，符合條件的直接輸出即可。這里set中的字符串已經按照默認字典序排序。完整程序如下：

習題5-6　對稱軸（Symmetry，ACM/ICPC Seoul 2004，UVa1595）

給出平面上N（N≤1000）個點，問是否可以找到一條豎線使得所有點左右對稱。如圖2.18所示，左邊的圖形有對稱軸，右邊沒有。

【分析】

如果存在對稱軸x＝m，那么m一定是所有點x坐標的平均值。首先在輸入每個點坐標的同時就求出m。然后遍歷每一個點p，要么p.x＝m就是說p關于x＝m的對稱點就是自身，或者p關于x＝m的對稱點也在輸入的點中，否則說明對稱軸不存在。

在輸入時就需要對所有的點建立索引，可以使用Point類，同時使用set＜Point＞來存儲所有的點，為此Point類需要重載“＜”比較運算符。

習題5-7　打印隊列（Printer Queue，ACM/ICPCNWERC 2006，UVa12100）

學生會里只有一臺打印機，但是有很多東西需要打印，因此打印任務不可避免的需要等待。有些打印任務比較急，有些不那么急，所以每個任務都有一個1～9的優先級，越大表示任務越急。

打印機的運作方式如下：首先從打印隊列里取出一個任務J，如果隊列里有比J更急的任務，則直接把J放到打印隊列尾部，否則打印任務J（此時不會把它放回打印隊列）。

輸入打印隊列中各個任務的優先級以及你所關注的任務在隊列中的位置（隊首位置為0），輸出該任務完成的時刻。所有任務都需要1分鐘打印。例如，打印隊列為｛1，1，9，1，1，1｝，目前處于隊首的任務最終完成時刻為5。

【分析】

使用STL中的queue來模擬打印隊列，同時因為需要判斷是否有更急的任務，那么就需要使用一個pCnt數組來維護每個優先級p在當前隊列中對應的任務的數量，需要在隊列變化時更新這個pCnt數組。完整程序如下：

習題5-8　圖書管理系統（Borrowers，ACM/ICPC World Finals 1994，UVa230）

你的任務是模擬一個圖書管理系統。首先輸入若干圖書的標題和作者（標題各不相同，以END結束），然后是若干指令：BORROW指令借書，RETURN指令還書。對于SHELVE指令，把所有已歸還但還未上架的圖書排序后依次插入到架子上并輸出圖書標題和插入位置（可能是第一本書或者某本書的后面）。

圖書排序的方法是先按作者從小到大排，再按標題從小到大排。在處理第一條指令之前，你應當先將所有圖書按照這種方式排序。

【分析】

首先建立一個Book類，使用一個vector＜Book＞來保存所有的圖書。同時使用map＜string，int＞建立一個標題到圖書編號（其在vector中的位置）的映射，方便根據標題來查找圖書。

使用兩個set＜int＞來分別保存已歸還但是還未上架的書籍shelf，以及還在書架上的書籍lib。set的第二個泛型參數（用于指定set內部對于Book類的排序規則）要使用一個函數對象（functor）來對其中的書籍位置按照題目要求的規則進行排序。

這樣借書還書時直接對shelf和lib進行操作即可。上架時，每次在lib中插入一個元素之后，可以取到這個元素在set中的位置iterator，然后對這個iterator進行自減操作即可拿到插入的書籍所在位置前面的一本書。完整代碼如下：

習題5-9　找bug（Bug Hunt，ACM/ICPC Tokyo 2007，UVa1596）

輸入并模擬執行一段程序，輸出第一個bug所在行。每行程序有兩種可能。

• □　數組定義：格式為arr［size］。如a［10］或者b［5］，可用下標分別是0～9和0～4。定義之后所有元素均為未初始化狀態。
• □　賦值語句：格式為arr［index］＝value。如a［0］＝3或者a［a［0］］＝a［1］。

賦值語句可能會出現兩種bug：下標index越界；使用未初始化的變量（index和value都可能出現這種情況）。

程序不超過1000行，每行不超過80個字符且所有常數均為小于2³¹的非負整數。

【分析】

建立一個Array類，里面包含數組的大小，并且用一個map＜int，int＞來表示初始化過的數組下標和對應的值。用size＝-1表示數組不存在，并且初始map是空的，表示每個位置上的元素均未初始化。之后在對每個語句求值時，遞歸求出每個表達式的值，然后再進行相應的賦值或者取值。另外，需要特別注意array的size＝0也是合法的。

習題5-10　在Web中搜索（Searching the Web，ACM/ICPC Beijing 2004，UVa1597）

輸入n篇文章和m個請求（n＜100，m≤50000），每個請求都是4種格式之一。

• □　A：找包含關鍵字A的文章。
• □　A AND B：找同時包含關鍵字A和B的文章。
• □　A OR B：找包含關鍵字A或B的文章。
• □　NOT A：找不包含關鍵字A的文章。

處理詢問時需要對每篇文章輸出證據。前3種詢問輸出所有至少包含一個關鍵字的行，第4種詢問輸出不包含A的整篇文章。關鍵字只由小寫字母組成，查找時忽略大小寫。每行不超過80字符，一共不超過1500行。

【分析】

首先在輸入時需要對所有的行進行記錄，把所有的行字符串放到一個vector＜string＞中，后續對行的處理都通過一個整數索引來進行。

經過仔細觀察可以發現，對于一個文章來說，所有的查詢都可以歸結為如下的操作：對于一個單詞w，查詢所有包含w的行的序號。由此可以對每一篇文章建立一個結構Doc，里面包含文章中所有的行的序號vector＜int＞ lines，以及一個map＜string，set＜int＞＞ words保存每個單詞的所在行號集合。這樣在每次插入行時就可以維護words以備后續查詢。

這個結構建立起來之后，對于AND和OR查詢，就是對查詢兩個單詞輸出的兩個set＜int＞進行set_union即可。對于NOT查詢，符合條件的文章就是查詢出來的結果為空的那些。對于每個單詞查詢，符合條件的文章就是查詢出集合不為空的那些。

另外一個技巧就是，針對set＜int＞提供一個operator＜＜的運算符重載，方便對查詢出來的行進行輸出。具體請參照以下代碼：

習題5-11　更新字典（Updating a Dictionary，UVa12504）

在本題中，字典是若干鍵值對，其中鍵為小寫字母組成的字符串，值為沒有前導零或正號的非負整數（因此－4、03和＋77都是非法的。注意該整數可以很大）。輸入一個舊字典和一個新字典，計算二者的變化。輸入的兩個字典中鍵都是唯一的，但是排列順序任意。具體格式如下（注意字典格式中不含任何空白字符）：

輸入包含兩行，各包含不超過100個字符，即舊字典和新字典。輸出格式如下。

• □　如果至少有一個新增鍵，打印一個“＋”號，然后是所有新增鍵，按字典序從小到大排列。
• □　如果至少有一個刪除鍵，打印一個“-”號，然后是所有刪除鍵，按字典序從小到大排列。
• □　如果至少有一個修改鍵，打印一個“*”號，然后是所有修改鍵，按字典序從小到大排列。
• □　如果沒有任何修改，輸出No changes。

例如，若輸入兩行分別為｛a：3，b：4，c：10，f：6｝和｛a：3，c：5，d：10，ee：4｝，輸出為以下3行：＋d，ee；-b，f；*c。

【分析】

對于每一行，使用一個線性遍歷把數據解析成map＜string，string＞，然后對兩個map進行對比，就可以判斷出所求的3種鍵。還建議對vector＜string＞重載operator＜＜操作符，方便對比較的結果進行輸出：

輸出結果的代碼就是這樣的：

習題5-12　地圖查詢（Do You Know The Way to San Jose？，ACM/ICPC World Finals 1997，UVa511）

有n張地圖（已知名稱和某兩個對角線端點的坐標）和m個地名（已知名稱和坐標），還有q個查詢。每張地圖都是邊平行于坐標軸的矩形，比例定義為高度除以寬度的值。每個查詢包含一個地名和詳細等級i。假定包含此地名的地圖中一共有k種不同的面積，則合法的詳細等級為1～k（其中1最不詳細，k最詳細，面積越小越詳細）。如果詳細等級i的地圖不止一張，則輸出地圖中心和查詢地名最接近的一張；如果還有并列的，地圖長寬比應盡量接近0.75（這是Web瀏覽器的比例）；如果還有并列，查詢地名和地圖右下角坐標應最遠（對應最少的滾動條移動）；如果還有并列，則輸出x坐標最小的一個。如果查詢的地名不存在或者沒有地圖包含它，或者包含它的地圖總數超過i，應報告查詢非法（并且輸出包含它的最詳細地圖名稱，如果有的話）。

【分析】

因為牽涉比較多的二維幾何計算，可以使用Point類來簡化相關代碼。首先是定義Map類，包含所有的相關信息（ratio, width, height, area, minx最小x坐標）等，并且需要對所有的地名的坐標建立索引，使用map<string, Point>。

對于每個具體的查詢，首先是根據坐標查出包含這個坐標的所有map以及相應的level值，之后需要對這些map進行排序，排序規則如題意所示。首先按照level（也就是面積從小到大）進行排序，level相同按照其他規則進行排序。排序規則可以封裝到一個STL的functor對象中去。完整程序如下：

習題5-13　客戶中心模擬（Queue and A，ACM/ICPC World Finals 2000，UVa822）

你的任務是模擬一個客戶中心運作情況。客服請求一共有n（1≤n≤20）種主題，每種主題用5個整數描述：tid、num、t0、t和dt，其中tid為主題的唯一標識符，num為該主題的請求個數，t0為第一個請求的時刻，t為處理一個請求的時間，dt為相鄰兩個請求之間的間隔（為了簡單情況，假定同一個主題的請求按照相同的間隔到達）。

客戶中心有m（1≤m≤5）個客服，每個客服用至少3個整數描述：tid，k，tid₁，tid₂，…，tid_k，表示一個標識符為pid的人可以處理k種主題的請求，按照優先級從大到小依次為tid₁，tid₂，…，tid_k。當一個人有空時，他會按照優先級順序找到第一個可以處理的請求。如果有多個人同時選中了某個請求，上次開始處理請求的時間早的人優先；如果有并列，id小的優先。輸出最后一個請求處理完畢的時刻。

【分析】

核心部分的邏輯是將所有要發生的事情用事件來表示，用優先級隊列來維護所有的事件，循環著每次從中取出最早的一個事件，然后按照事件類型進行分類處理：

輸入時，每種請求就實現生成num個事件放到事件隊列中。模擬的循環中，每個時間點，用multiset＜int＞作為要服務的請求隊列，使用multiset是因為隊列中可能有相同主題的請求。同時用一個set維護空閑的客服編號。

首先取出所有時間相同的隊首事件，挨個進行處理。

（1）如果是請求事件，就放到請求隊列。

（2）如果是客服事件，就將客服加到空閑客服集合中。

然后就是針對當前空閑客服以及請求隊列中的請求進行匹配處理。

while(請求隊列非空& &空閑客服集合非空) {

（1）針對每個請求建立一個集合set<int>，放置所有可以服務此請求的客服編號，編號排序規則參考題目的表述。

（2）先將每個客服按照優先級分配到其能處理的每個任務的集合中。

（3）如果沒有進行分配，直接退出while循環。

（4）按照之前分配好的任務集合給客服分配任務，對于每個分配好的客服，要構造一個其變為空閑的事件，放入事件隊列。

}

完整程序如下：

此類離散事件模擬類的題目最關鍵是要掌握事件概念的抽象方法以及優先級隊列的使用。習題5-16也可以作為很好的練習題目。

習題5-14　交易所（Exchange, ACM/ICPC NEERC 2006, UVa1598）

你的任務是為交易所設計一個訂單處理系統。要求支持如下3種指令。

• □　BUY p q：有人想買，數量為p，價格為q。
• □　SELL p q：有人想賣，數量為p，價格為q。
• □　CANCEL i：取消第i條指令對應的訂單（輸入保證該指令是BUY或者SELL）。

交易規則如下：對于當前買訂單，若當前最低賣價（ask price）低于當前出價，則發生交易；對于當前賣訂單，若當前最高買價（bid price）高于當前價格，則發生交易。發生交易時，按供需物品個數的最小值交易。交易后，需修改訂單的供需物品個數。當出價或價格相同時，按訂單產生的先后順序發生交易。輸入輸出細節請參考原題。

【分析】

表面上來看，買賣都是一個優先級隊列，但是這里有一個需求就是需要隨時從隊列中刪除一個元素，如果用heap實現（STL中的priority_queue就是基于heap實現），刪除的時間會比較長：需要從vector中刪除然后重新構造heap。

所以可使用set<int>來實現隊列，隊列中保存的是Order的編號，先按照價格排序，再按照訂單的先后順序也就是編號的大小排序。因為兩個隊列的排序規則不同，將兩個規則分別封裝成為兩個functor對象，然后將其作為泛型參數來聲明兩個不同的set即可。完整程序如下：

習題5-15　Fibonacci的復仇（Revenge of Fibonacci, ACM/ICPC Shanghai 2011, UVa12333）

Fibonacci數的定義為F(0)=F(1)=1，然后從F(2)開始，F(i)=F(i-1)+F(i-2)。例如前10項Fibonacci數分別為1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

有一天晚上，你夢到了Fibonacci，它告訴你一個有趣的Fibonacci數。醒來以后，你只記得它的開頭幾個數字。你的任務是找出以它開頭的最小Fibonacci數的序號。例如以12開頭的最小Fibonacci數是F(25)。輸入不超過40個數字，輸出滿足條件的序號。

如果序號為0～100000（不包含100000）的Fibonacci數均不滿足條件，輸出-1。

【分析】

如果直接用十進制大整數類，計算就會超時。可以使用一萬進制的大整數類。依次求出前99999個F數，但是不需要每次保存F數本身，只是把其前40位作為字符串保留下來，存儲到一個Trie中去。后續查找就在這個Trie中查找。

關于Trie的介紹請參考《算法競賽入門經典—訓練指南》中的3.3.1節。完整程序如下：

習題5-16　醫院設備利用（Use of Hospital Facilities, ACM/ICPC World Finals 1991, UVa212）

醫院里有n（n≤10）個手術室和m（m≤30）個恢復室。每個病人首先會被分配到一個手術室，手術后會被分配到一個恢復室。從任意手術室到任意恢復室的時間均為t₁，準備一個手術室和恢復室的時間分別為t₂和t₃（一開始所有手術室和恢復室均準備好，只有接待完一個病人之后才需要為下一個病人準備）。

k名（k≤100）病人按照花名冊順序排隊，T點鐘準時開放手術室。每當有準備好的手術室時，隊首病人進入其中編號最小的手術室。手術結束后，病人應立刻進入編號最小的恢復室。如果有多個病人同時結束手術，編號較小的病人優先進入編號較小的恢復室。輸入保證病人無須排隊等待恢復室。

輸入n、m、T、t₁、t₂、t₃、k和k名病人的名字、手術時間和恢復時間，模擬這個過程。輸入輸出細節請參考原題。

【分析】

首先是定義事件結構：

類似于習題5-13，可以定義以下幾個事件類型：

（1）手術室開始進入空閑狀態opFree。

（2）手術室開始進入準備狀態opPre。

（3）恢復室開始進入空閑狀態reFree。

（4）恢復室開始進入準備狀態rePre。

建立幾個全局狀態：

（1）等待做手術的病人隊列opQueue。

（2）等待進恢復室的病人隊列reQueue。

（3）空閑手術室隊列freeOpRooms。

（4）空閑恢復室隊列freeReRooms。

（5）事件隊列(使用priority_queue)。

以上1～4全局狀態均使用set，因為需要針對編號進行排序，需要注意的是reQueue的排序規則，是按照病人之前做手術時所在的手術室編號進行排序。

整個模擬的過程就是循環地進行事件的處理。

1．處理當前時間的事件

（1）對于opFree，就是將手術室插入freeOpRooms。

（2）對于opPre，說明手術室開始準備，病人做完手術了，需要把這個病人插入reQueue，并且往事件隊列中插入一個手術室準備完畢也就是一個opFree的事件。

（3）對于reFree，就是將恢復室插入freeReRooms。

（4）對于rePre，說明病人做完恢復了。往事件隊列中插入一個恢復室準備完畢的事件。

2．分別處理opQueue和reQueue

（1）對于opQueue和freeOpRooms，按照題目規則把病人安排到對應的手術室，并且按照病人的手術時間插入opPre事件。同時增加病人以及手術室的對應時間信息。

（2）對于reQueue和freeReRooms，按照題目規則把病人安排到對應的恢復室，并且按照病人的恢復時間插入rePre事件。同時增加病人以及恢復室的對應時間信息。

完整程序如下：