2.6　高效算法設計

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

習題8-1　裝箱（Bin Packing，SWERC 2005，UVa1149）

給定N（N≤10⁵）個物品的重量L_i，背包的容量M，同時要求每個背包最多裝兩個物品。求至少要多少個背包才能裝下所有的物品。

【分析】

先對N個物體按照重量從大到小排序。依次進行決策。在沒放好的物體中，考慮最重的i，它應該和誰放一起呢？選擇最輕的j，如果i＋j都放不到一個背包里，那i只能單獨放，否則就把i和j放在一起。

在考慮i時，如果有多個j都可以和i放在一起，那么選擇最輕的j是不是最優策略？對于所有比j重的k來說，在i決策完之后考慮的物體，重量小于i，所以k依然可以和i之后的物體放在一起，不會多占背包。完整程序如下：

習題8-2　聚會游戲（Party Games，Mid-Atlantic 2012，UVa1610）

輸入一個n（2≤n≤1000，n是偶數）個字符串的集合D，找一個字符串（不一定在D中出現）S，使得D中恰好一半串≤S，另一半串＞S。如果有多解，輸出字典序最小的解。例如，對于｛JOSEPHINE，JERRY｝，輸出JF；對于｛FRED，FREDDIE｝，輸出FRED。

【分析】

記n＝2k。首先對D進行遞增排序，所求的字符串P一定滿足D_k≤P＜D_k＋1，則問題就變成尋找符合這個條件的最短并且字典序最小的字符串。記D_k的長度為L，則P的長度一定不大于L。參考暴力搜索的思路，從P的最左邊第0位到第L-1位逐步從小到大嘗試構造每一位的字符。對于第i位，開始令P［i］＝‘A‘，只要滿足P［i］≤‘Z‘且P＜D_k，就一直令P［i］遞增。這樣構造出來的P［i］如果滿足P［i］≤‘Z‘且D_k≤P＜D_k＋1，則說明構造完成，否則繼續構造下一位。每一位構造完成之后所得的P就是所求的解。完整程序如下：

習題8-4　獎品的價值（Erasing and Winning，UVa11491）

你是一個電視節目的獲獎嘉賓。主持人在黑板上寫出一個N位整數（不以0開頭），并邀請你恰好刪除其中的D個數字。剩下的整數便是你所得到的獎品的價值。自然地，你希望這個獎品價值盡量大。1≤D＜N≤10⁵。

【分析】

令E＝N–D，則本題就是要從輸入的整數中選擇E個數字，使得組成的整數最大。可以連續選擇E次最左邊的最大數字，還要給后續的選擇留夠位數，每次選擇的位置為pos，則下次選擇的范圍就從pos＋1開始。

注意有一個子操作：從一個區間內選擇最左邊的最大數字。因為N和D的規模都比較大，如果每次線性查找，最壞情況下的時間復雜度會達到O（N²）級別，對于輸入的規模是無法接受的⁽¹⁾。可以做如下的預處理：對于每個位置i以及d∈［0，9］，記錄在區間［i…］內第一個d出現的位置NEXT［i］［d］。這個預處理可以在O（10n）的時間內完成，然后上述子操作就可以在O（9）的時間內完成。

完整程序如下：

習題8-5　折紙痕（Paper Folding, UVa177）

你喜歡折紙嗎？給你一張很大的紙，對折以后再對折，再對折……每次對折都是從右往左折，因此在折了很多次以后，原先的大紙會變成一個窄窄的紙條。現在把這個紙條沿著折紙的痕跡打開，每次都只打開“一半”，即把每個痕跡做成一個直角，那么從紙的一端沿著和紙面平行的方向看過去，會看到一個美妙的曲線，如圖2.43所示。

例如，如果你對折了4次，那么打開以后你將看到如圖2.43所示的曲線。注意，該曲線是不自交的，雖然有兩個轉折點重合。給出對折的次數，請編程繪出打開后生成的曲線。

【分析】

看到題目很多讀者應該會和筆者一樣，首先想到去直接模擬折疊過程。

但經過思考可以發現一個關鍵點：可以忽略折疊的過程。直接從一條水平的單位長度的線段開始張開，每次張開都是把已有的所有線段首先圍繞一個點順時針旋轉90°，然后再和旋轉之前的線段一起組合成為新的圖形。每次旋轉的過程中，需要維護兩個點的坐標：起始點s和旋轉中心點rot。每次旋轉，原先的s不變，s經過旋轉之后的那個點成為新的rot，如圖2.44所示。

旋轉的次數就是輸入的n。

當把所有最終線段的坐標模擬出來之后，就剩下輸出的問題。有一種比較簡便的處理方法就是掃描所有的線段，將其x坐標放大一倍，然后垂直類型線段的x坐標再減1。判斷平面上每個點是否有垂直或者水平線段，記錄對應的字符。最后再掃描平面上的每個點，輸出之前記錄的字符即可。

完整程序如下：

習題8-6　起重機（Crane，ACM/ICPC CERC 2013，UVa1611）

輸入一個1～n（1≤n≤10000）的排列，用不超過9⁶次操作把它變成升序。每次操作都可以選一個長度為偶數的連續區間，交換前一半和后一半。如輸入5, 4, 6, 3, 2, 1，可以執行1, 2先變成4, 5, 6, 3, 2, 1，然后執行4, 5變成4, 5, 6, 2, 3, 1，然后執行5, 6變成4, 5, 6, 2, 1, 3，然后執行4, 5變成4, 5, 6, 1, 2, 3，最后執行操作1,6即可。

【分析】

這道題目要求排序，但是基本操作卻是“交換一個偶數長度的連續區間的前后兩半”，依然可以使用冒泡排序的思路，依次把1到n的每個數歸位。

遍歷到數字i時，此時1～i-1已經排好序，在未排序的區間（長度是n-i+1）中，記i前面的元素個數為ci，則有以下兩種情況。

（1）ci≤(n-i+1)/2，那么可以通過將i前面的未排序區間（記其長度為ci）和從i開始長度為ci的區間進行交換，即可把i交換到第i個位置。

（2）否則，如果n-i+1是偶數，交換前后兩半，然后按照情況1處理即可。如果n-i+1是奇數，則忽略第一個元素（肯定不是i），交換剩下長度為偶數的區間的前后兩半。

這樣在≤2n次操作之內就可以完成。

對于輸入數據(5 4 6 3 2 1)，算法的運行過程示意圖如下，其中灰色表示未排序區間。

完整程序如下：

習題8-8　猜名次（Guess, ACM/ICPC Beijing 2006, UVa1612）

有n（n≤16384）位選手參加編程比賽。比賽有3道題目，每個選手的每道題目都有一個評測之前的預得分（這個分數和選手提交程序的時間相關：提交得越早，預得分越大）。接下來是系統測試。如果某道題目未通過測試，則該題的實際得分為0分，否則得分等于預得分。得分相同的選手，ID小的排在前面。

給出所有3n個得分以及最后的實際名次，問是否可能。如果可能，輸出最后一名的最高可能得分。每個預得分均為小于1000的非負整數，最多保留兩位小數。

【分析】

考慮每個選手，每道題目的得分有兩種可能（預得分或0），那么總得分就是2³=8種可能。輸入時，就計算每個選手的這8種得分并且從大到小排序。

第一名的得分選擇為8個得分中的最大值，然后按照名次從前到后遍歷每個選手，從其8個可能得分中選擇滿足以下條件的最大得分：

（1）小于上個選手的得分。

（2）或者等于上一個選手的得分且ID小于其ID。

如果選擇成功，則這個得分必定是當前選手符合輸入名次的最大可能得分。如果失敗，說明這個名次無法構造，直接退出。所有選手選擇成功后，直接輸出最后一個選手選擇的得分。

需要注意的是，雖然分數是浮點數，但是題目標明了只有小數點后兩位。所以可以直接乘以100轉換為整數，最后輸出時再除以100。為了避免轉換誤差，在輸入時作為字符串輸入，然后再讀取為兩個int。輸出時做類似的處理。完整程序（C++11）如下：

習題8-11　高速公路（Highway, ACM/ICPC SEERC 2005, UVa1615）

給定平面上n（n≤10⁵）個點和一個值D，要求在x軸上選出盡量少的點，使得對于給定的每個點，都有一個選出的點離它的歐幾里得距離不超過D。

【分析】

對于每個指定的點P，X軸上符合要求的點剛好組成X軸和圓（P,D）相交的那根弦所對應的區間。那么題目就轉換為，在一系列的區間內選擇最少的點，使得每個區間內都有點被選中。具體的思路可參考《算法競賽入門經典（第2版）》中的第8.4.2節。

習題8-14　商隊搶劫者（Caravan Robbers, ACM/ICPC NEERC 2012, UVa1616）

輸入n條線段，把每條線段變成原線段的一條子線段，使得變之后所有線段等長且不相交（但是端點可以重合）。輸出最大長度（用分數表示）。例如，有3條線段[2,6]、[1,4]、[8,12]，則最優方案是分別變成[3.5,6]、[1,3.5]、[8,10.5]，輸出5/2。

【分析】

首先把所有線段按照左端點從小到大進行排序，然后使用二分法來計算子線段的最大長度。對于長度L，針對每一個原線段[a,b]，盡量選擇靠左的區間作為子線段，如果子線段的左端點max(a,lb)+L > b，那么選擇失敗，其中lb是上一個選擇的子線段的右端點。如果每個線段選擇成功，那么L有效。

但是需要注意以下幾點：

（1）二分開始要選擇盡量窄的一個起始區間，可以選擇為[1, 1000000/n]。

（2）二分的迭代次數50次就足夠，無須將區間縮小到足夠小的范圍，否則會超時。

（3）選擇輸出目標的有理數時，遍歷所有可能的分母（就是1～n），然后根據分母以及算出的長度來選擇分子。最后選擇誤差最小的分子分母組合來輸出，輸出之前都要除去二者的最大公約數。

完整程序如下：

習題8-16　弱鍵（Weak Key，ACM/ICPC Seoul 2004，UVa1618）

給k（4≤k≤5000）個整數組成的序列N_i，判斷是否存在4個整數N_p、N_q、N_r和N_s（1≤p＜q＜r＜s≤k），使得N_q＞N_s＞N_p＞N_r或者N_q＜N_s＜N_p＜N_r。

【分析】

首先對輸入序列做預處理，對于每個N_i，記錄兩個序列H_i和L_i。H_i包含所有的j，j＞ i且N_j＞ N_i。L_i包含所有j，j滿足j＞i且N_j＜N_i。

然后就是遍歷所有的p，依次選擇可能的q、r、s。

以N_q＜N_s＜N_p＜N_r為例：

（1）q肯定在L_p中，在其中進行遍歷。

（2）p、q確定之后，r肯定在H_p中并且r＞q，使用upper_bound在H_p中查找所有可能的r。

（3）p、q、r確定之后，s肯定在H_q以及L_p中，并且s＞r，使用upper_bound查找結合binary_search判斷。

依次進行查找，如果查找到s說明有解。查找的過程中判斷數字是否在某個序列中并且大于一個數，都可以使用二分查找。可以使用STL中的binary_search和upper_bound。完整程序如下：

習題8-17　最短子序列（Smallest Sub-Array，UVa11536）

有n（n≤10⁶）個0～m-1（m≤1000）的整數組成一個序列。輸入k（k≤100），你的任務是找一個盡量短的連續子序列（x_a，x_a＋1，x_a＋2，…，x_b-1，x_b），使得該子序列包含1～k的所有整數。

例如n＝20，m＝12，k＝4，序列為1（2 3 7 1 12 9 11 9 6 3 7 5 4）5 3 1 10 3 3，括號內部分是最優解。如果不存在滿足條件的連續子序列，輸出“sequence nai”（不含引號）。

【分析】

使用滑動區間的思路，維護一個區間［L，R］，以及一個map，其中包含了［L，R］所有1～k的整數，及其出現的次數。需要注意的是，map中只插入1～k的整數。則當map大小為k時［L，R］就是一個符合要求的區間。

首先L＝0，不斷增加R，直到map的大小等于k為止，當map的大小為k時，只要L對應的整數x不在1～k的范圍內或者x在map中出現的次數大于1，就可以安全地從區間中刪除x，如此反復，當無法繼續刪除L時，就是一個潛在的最小區間。

當發現一個最小區間之后，就把L加1，讓區間向右滑動，然后再尋找小區間。如此在滑動的過程中記錄下出現的最短區間。完整程序如下：

習題8-18　感覺不錯（Feel Good，ACM/ICPC NEERC 2005，UVa1619）

給一個長度為n（n≤100000）的非負整數序列a_i，求出一段連續子序列a_l，…a_r，使得（a_l＋…＋a_r）*min｛a_l，…，a_r｝盡量大。

【分析】

對于一個區間［l，r］來說，我們稱所求的值為它的權值。假如a_r＋1不是［l，r＋1］區間的唯一最小值，那么［l，r＋1］的權值一定大于［l，r］的。對于每個i，假如能讓a_i成為最小值的最大區間是［l_i，r_i］，則只需要對所有的［l_i，r_i］求權值比較即可。

首先需要預處理出以下數組：

（1）A的前綴和數組S，其中 。

（2）L和R數組，其中L_i表示i左邊離i最近且比a_i小的元素位置。R_i就是i右邊離i最近的比a_i小的元素。讓a_i成為最小值的最大連續區間就是［L_i，R_i］。

其中第二個預處理的單調棧算法如下（以L_i為例）。

首先，在數組A前后各附加1個0。使用一個棧S，初始為空。從左到右把所有下標i＝1～n入棧，每個下標i入棧之前，首先把所有a_j≥a_i的下標j出棧，之后，棧頂就是左邊最接近并且小于a_i的元素下標，也就是L_i的值。處理完即可得到L數組。

以A＝｛3，1，6，4，5，2｝為例，演示此算法的運行過程。

初始S＝｛｝，A＝｛0，3，1，6，4，5，2，0｝

i=1:A［1］=3, L［1］=0, S=｛1｝

i=2:A［2］=1, L［2］=0, S=｛2｝

i=3:A［3］=6, L［3］=2, S=｛2,3｝

i=4:A［4］=4, L［4］=2, S=｛2,4｝

i=5:A［5］=5, L［5］=4, S=｛2,4,5｝

i=6:A［6］=2, L［6］=2, S=｛2,6｝

再用類似的邏輯從右到左處理一次即可得到R數組。預處理完成后，計算所有a_i*（S_Li＋1-S_Ri）的最大值即可。需要注意的是，可能會有一種特殊情況就是全部元素為0，則所求結果就是0，所在區間為［1，1］，需要進行特殊處理。完整程序（C＋＋11）如下：

習題8-19　球場（Cricket Field，ACM/ICPC NEERC 2002，UVa1312）

一個W*H（1≤W，H≤10000）網格里有n（0≤n≤100）棵樹，要求找一個最大空正方形，如圖2.45所示。

【分析】

注意網格的長寬都很大，直接枚舉正方形的邊界（時間復雜度為10000³）會超時。但是樹只有最多100棵，且正方形內部肯定不能包含樹。另外，最大正方形一定是有至少兩條邊都經過一棵樹（包括網格邊界），如圖2.46所示，否則很容易構造出更大的正方形。

遍歷正方形的邊界。首先對所有樹的Y坐標排序去重（使用set即可），得到一個正方形可能的上下邊的Y坐標集合，再對所有樹的坐標按照X進行排序。

枚舉正方形的上下邊的Y坐標。對于每一對Y坐標（minY，maxY），初始的正方形左邊界為left＝0（操場左邊）。對于所有的樹坐標P，如果P．y恰好正在枚舉的上下邊界之間，那么就發現一個新的正方形位于（left，P．x）以及（minY，maxY）相交形成的區域內，更新答案。同時更新P．x為下一個正方形的左邊界。時間復雜度是O（n³）。注意整個網格的邊界也可以理解為樹，不要忘記處理。完整程序如下：

習題8-24　龍頭滴水（Faucet Flow，UVa10366）

x＝0的正上方有一個水龍頭，以每秒1單位體積的速度往下滴水。x＝-1，-3，…，leftx和x＝1，3，5，…，rightx處各有一個擋板，高度已知。求經過多長時間以后水會流出最左邊的擋板或者最右邊的擋板。如圖2.47所示，leftx＝-3，rightx＝3，4個擋板高度分別為4、3、2、1，則6秒鐘之后水會從最右邊的擋板溢出。

輸入第一行為兩個奇數leftx和rightx（leftx≤-1，rightx≥1），接下來的各個正整數表示從左到右各個擋板的高度。擋板個數不超過1000。

【分析】

首先引入一個關鍵的結論：

如果有兩個擋板X和Y（如圖2.48所示），X不高于Y，那么從X左邊的水如果要流到Y，在接觸到Y之前，會形成一個階梯形狀。也就是說，從X流到Y所需要的時間就是階梯下方的面積。

回到題目本身，考慮X＝0的左右兩邊最高的擋板高度LH、RH，以及其位置LHi、RHi（如果有多個，就取離X＝0最近的那個）。

如果LH＝RH，那么說明水流會在兩邊都溢出來。那么就計算水從LHi流到最左邊擋板所需要的時間Lt，以及從RHi流到最右邊擋板所需要的時間Rt。因為兩邊同時在流，所求的結果就是水把LHi-RHi這個區間的矩形裝滿所需要的時間再加上min（Lt＋Rt）*2。

如果LH＜RH，假設Ti是X＝0右邊第一個高度≥LH的，如圖2.49所示。

那么水一定是首先接觸到左邊緣。而且水流分兩部分，一部分從Ti流到Ti右邊第一個高度大于LH的擋板的位置這里，另一部分從LHi向左溢出流到左邊緣。假設前者所需水量為rt，后者所需為lt。

（1）如果lt＞rt，那么所求結果就是：LHi和Ti之間高度為LH的矩形對應的水量也就是（LHi＋Ti）*LH＋lt＋rt。

（2）如果lt≤rt，rt對應的部分只能灌滿lt的水，左邊就已經溢出了，所求結果就是：（LHi＋Ti）*LH＋2*lt。

LH＞ RH時的討論可以類比以上情況。

為了簡化處理，可以先假設兩個擋板之間距離為1，最后求出結果之后再乘以2輸出即可。完整程序如下：

習題8-25　有向圖D和E（From D to E and back，UVa11175）

對一個有n個結點的有向圖D，可以構造這樣一個圖E，即D的每條邊對應E的一個結點（例如，若D有一條邊uv，則E有個結點的名字叫uv），對于D的兩條邊uv和vw，E中的兩個結點uv和vw之間連一條有向邊。E中不包含其他邊。

輸入一個m個結點k條邊的圖E（0≤m≤300），判斷是否存在對應的圖D。E中各個結點編號為0～m-1。

【分析】

在E圖中，如果存在i和j結點到x都有邊，而i和j中只有一個結點到y有邊，則這個圖E不可能轉化來，因為在D中一條邊不可能指向兩個點（讀者可以參考圖2.50來思考）。因此暴力枚舉i、j和x判斷是否可行即可。

完整程序（C＋＋11）如下：

習題8-26　找黑圓（Finding ［B］lack Circles，Rujia Liu's Present 6，UVa12559）

輸入一個h*w的黑白圖像（30≤w，h≤100），你的任務是找出圖像中的圓。每個像素都是1*1的正方形，左上角像素的中心坐標為（0，0），右下角像素的中心坐標為（w-1，h-1）。對于一個圓，它的圓周穿過（只是接觸到像素邊界不算）的像素都會被涂黑（用1表示）。沒有被任何圓穿過的像素仍然是白色（用0表示）。圓心保證在整點處，半徑保證是1～5的整數。最多有2%的黑點會變成白點。

【分析】

因為數據量不是特別大，所有可能的圓的個數上限是50*30*100，可以考慮進行暴力搜索每一種可能的半徑以及坐標（r，x，y）。

對于（r，x，y）來說，要循環判斷圓上的每個點，因為邊上的點最多也就是100個。可以遍歷100個圓心角角度對應的點來判斷，為了提高速度，可以采用如下技巧：

（1）隨機取100個角度，看看這個角度對應的邊上的點是不是存在。

（2）如果已經判斷超過10個且有一半不符合，說明一定不存在對應的圓，直接返回即可。

完整程序如下：