--- # System prepended metadata title: AP325-Python 第4章 貪心演算法與掃瞄線演算法 (I) tags: [AP325, python, apcs] --- # AP325-Python 第4章 貪心演算法與掃瞄線演算法 「貪心通常比較簡單，但多半不能解決問題，在演算法與人生中都是這樣。」 孔子說：「及其老也，血氣既衰，戒之在得。」日常生活中最常看到貪的狀況就是政治人物，而想到政治人物就想到金庸的笑傲江湖。這一章的例題習題部分就以笑傲江湖中的人物來串場，不過不必擔心，沒看過故事不影響解題。 --- 這一章介紹貪心演算法(Greedy algorithm)以及掃描線演算法(sweep-line algorithm)，這兩種演算法有點類似，所以放在同一章。這裡的貪心沒有負面的意思，單純指以當前最有利的方式做決定。貪心演算法通常很直覺，所以寫程式往往簡單，但不是對所有問題都能夠找到最佳解。Greedy通常需要證明，但上機考試與競賽的場合，不需要證明，所以很多人不知道怎麼做的時候就用Greedy寫下去猜猜看，考試本來就是該猜就要猜，不過貪心也要貪的正確。 掃描線演算法的名字出自計算幾何，是指解題過程想像用一條掃描線沿著某個方向掃描過去，他是一個很好的思考模式，很多經典的分治演算法都有掃瞄線的版本。有一些數列的問題往往可以看成數線上的問題，所以也可以用掃描線的方式來思考。 貪心演算法與掃描線演算法通常需要搭配排序或優先佇列(priority_queue，常簡稱PQ)，我們在第二章介紹過排序了，所以這裡不再重複。優先佇列是一種重要的資料結構，在大部分資料結構的課本中都有介紹自製的方法(heap)以及應用，它在Python中也有庫存函數可以呼叫，但它應該不能算「常用簡單」的資料結構，所以在APCS考試中應該不會出現非用它不可的題目，我們會對PQ做簡單的介紹。 ## 基本原理 所謂貪心演算法指的是：**一個算法由一連串的決定組成，每次決定時都以當時最有利的方式挑選，而且一旦挑選後就不再更改**。我們先以舉一個很簡單的例子來說明。 --- ##### P-4-1. 少林寺的代幣 令狐沖去少林寺觀光，少林寺有四種代幣，面額分別是$(1, 5, 10, 50)$，令狐沖拿了 $n$ 元去換代幣，請問以這四種代幣湊成 $n$ 元，最少要多少枚代幣？ Time limit: 1秒 輸入格式：第一行是一個正整數 $m$，代表有幾筆測資，以下有 $m$ 行，每行是一筆測資，每筆測資是一個正整數 $n$，$n<1000$。 輸出：依序每一行輸出每一筆測資的最少的代幣數量。 範例輸入： 3 21 50 123 範例結果： 3 1 7 說明：$21 = 10\times 2 + 1$, $50 = 50\times 1$, $123 = 50\times 2 + 10\times 2 + 1\times 3$。 --- 因為代幣的數量希望要最少，直覺貪心的想法就是要盡量使用面額大的硬幣，代幣由大面額的往小的考慮，能換盡量換，剩下不足的再考慮比較小的面額。以下是這樣的程式。 ```python= # P-4-1 num of coin, greedy m = int(input()) coin = [1,5,10,50] for i in range(m): n = int(input()) num = 0 for c in coin[::-1]: # large to small num += n//c # num of coin c n %= c # remaining print(num) # ``` 程式寫起來很簡單，簡單到如果考試碰到這種題目，會懷疑是不是有陷阱。這個方法很直覺，但怎麼知道它是對的呢？有些人可能會說：就很直覺啊，路邊隨便找個少林寺掃地的也會這樣做。 那麼請看看下面的狀況：假設代幣的面額是$(1, 4, 5)$三種，上面的貪心方法會找到正確答案嗎？假設$n=8$，貪心的方法會先換一個5元，然後剩下3元就換3個1元代幣，所以8元換了4個代幣。但是如果拿兩個4元代幣就可以湊8元了，所以正確答案應該是2而不是4。 請不要懷疑人生，P-4-1的做法是對的，只是並不是能用在任何代幣面額的狀況，我們必須證明。如何證明呢？ 在代幣是$(1, 5, 10, 50)$的情形下，如果1元的代幣總額不小於5，一定可以拿出5個換成一個5元，所以1元代幣的個數不會超過4個；同樣的你可以證明5元代幣不會超過1個，10元代幣不會超過4個。也就是說，對任意第$j$種代幣$coin[j]$，小於$coin[j]$的代幣總額不會超過$coin[j]$，所以Greedy是對的。在$(1, 4, 5)$的狀況，就沒有這個性質了。順便一提，不要小看少林寺的掃地僧，掃地僧往往是最厲害的。 這個例子中我們看到了貪心法的一些特質。 * 算法由一連串決定組成(由大到小逐一考慮各種代幣的數量)，每次考慮當前最好決定(能換盡量換)，選擇後就不再更改。 * 算法的正確性必須經過證明，內容就是要證明所下的決定是對的，也就是一定有一個最佳解包含了貪心法所做的決定，而證明的方法通常都是用換的：假設有一個最佳解跟貪心法做的決定不一樣，那麼，我們可以換成一個與貪心法一樣的決定，而解會更好，或至少不會變差。 在下一節中我們會看到更多的例子。貪心算法往往都是要不斷的找最大值或最小值，如果資料不會變動，可以在開始的時候做一次排序，如果資料是會變動的呢？就必須用一個動態的資料結構來處理，以下我們對優先佇列做一點介紹。 ### 優先佇列 (priority_queue) (\*) 第三章介紹過佇列，佇列跟現實生活中排隊的狀況一樣，是先進者先出，但更貼近現實生活中的狀況是有些事情後發生的卻必須先處理，因為緊急或是更重要。 優先佇列就是具有優先權的排列，不管進入的順序，優先權高的會排在前面。Python標準函數庫中的heapq提供了PQ基本操作函數，資料結構的課本中也都有教以heap來實作，heap是一個完全二元樹(complete binary tree)，但實作在陣列中，也就是心中有樹但程式中沒有樹。heap的實作並不算困難，但考試與比賽時間寶貴，通常能使用內建的就不要自己寫，因此本書中並不介紹heap的實作，有興趣的可以人可以自己查詢網路或書籍。 Python的heapq說明可以參考[heapq --- 堆積佇列 (heap queue) 演算法](https://docs.python.org/zh-tw/3/library/heapq.html)，使用時自己準備一個list，然後呼叫它所提供的函數來對list進行操作。常用操作的時間複雜度如下，其中$n$表示成員的數量，也就是佇列的大小： * 加入新元素(push)，$O(\log n)$。 * 查詢最小值(top)，$O(1)$。 * 刪除最小值(pop)，$O(\log n)$。 * 檢查是否為空(empty)，$O(1)$。 請注意刪除與查詢只能針對最小值，若要改變大小順序，最簡單的方法就是改變key的正負號。以下的範例程式介紹基本用法，說明請見程式內註解。 ```python= import heapq h1 = [] # initial empty list as heap heapq.heappush(h1, 5) # push, O(logn) for v in [4,1,5]: heapq.heappush(h1, v) # print(h1,"min is ",h1[0]) # min element at [0] q = heapq.heappop(h1) # pop min to q, O(logn) print("previous min =",q, "current min =",h1[0]) print("current size:",len(h1)) # size of heap O(1) if len(h1): print('not empty') # check if empty O(1) else : print('empty') a = [2,-4,-5,-4,8] # initial from a list heapq.heapify(a) # initial a nonempty heap, O(n) print(a,"min =",a[0]) # min at top a.sort() # can also initialized by sort but O(nlogn) # to make a max-heap, using -v for b = [-x for x in a] print("minus value of a =",b) heapq.heapify(b) imax = -heapq.heappop(b) # original max in a print("max of a is",imax) # element can be list a = [2,-4,-3,-4,8] pa = [[v,i] for i,v in enumerate(a)] #[value,index] print(a); print(pa) heapq.heapify(pa) v,i = heapq.heappop(pa) print("min of a is a[",i,"] = ",v) ``` 輸出結果如下： ``` [1, 5, 4, 5] min is 1 previous min = 1 current min = 4 current size: 3 not empty [-5, -4, 2, -4, 8] min = -5 minus value of a = [5, 4, 4, -2, -8] max of a is 8 [2, -4, -3, -4, 8] [[2, 0], [-4, 1], [-3, 2], [-4, 3], [8, 4]] min of a is a[ 1 ] = -4 ``` ## 例題與習題 這一節我們來看貪心與掃瞄線演算法的題目，我們將題型區分為以下幾類，每一類挑選一些經典題來說明，另外在下一節有一些其他的補充習題： * 單欄位資料排序 * 多欄位資料排序 * 以PQ處理動態資料 * 貪心搭配二分搜 * 掃描線演算法 很多貪心算法的重點在證明，但本書以程式實作為主，不以證明為重點，所以有些題目的證明只簡略說明重點，或者請讀者上網路查詢。 ### 單欄位資料排序 --- ##### P-4-2. 笑傲江湖之三戰 笑傲江湖的遊戲中，你扮演令狐沖的角色，因為「長恨此身非我有，何時忘卻盈盈」，所以你率領任我行等魔教高手前往少林寺搭救任盈盈，欲知故事原委可參見笑傲江湖第27回「三戰」。 套句丸尾班長的口頭禪，總而言之，少林寺與五嶽劍派等正教派出$n$位高手，而你方也有$n$位高手，每個人都有一個戰力值。雙方要進行一對一的對戰，每個人不管輸或贏都只能比一場，假設兩人對戰時，戰力值高的獲勝。對於對方的每一位高手，你可以指定派哪一位與其對戰，為了解救盈盈，你希望贏越多場越好，平手則沒有幫助。請計算出最多能贏多少場。 Time limit: 1秒 輸入格式：第一行是一個正整數$n$，第二行有$n$個非負整數是對方的戰力，第三行有$n$個非負整數是我方的戰力，同行數字間以空白間格。$n$與戰力值不超過1e5。 輸出：輸出最多可能的勝場數。 範例輸入： 5 3 1 7 0 2 8 3 5 0 0 範例結果： 3 --- 我們只要關心可以戰勝的那些場次需要誰去出戰，其他場次贏不了，就在剩下的人裡面隨便挑選去應戰。假設我方目前最弱的戰力是$a$而對方最弱的是$b$，如果$a \le b$，則$a$對誰都不會贏，是沒用的，可以忽略。否則$a > b$，我們宣稱「一定有一個最佳解是派$a$去出戰$b$」，證明如下： 假設在一個最佳解中，$a$對戰$x$而$y$對戰$b$，我們將其交換改成「$a$對$b$而$y$對$x$」。根據我們的假設$y \ge a$，交換後$a$可以贏$b$而$y$對$x$的戰績不會比$a$對$x$差，所以交換後勝場數不會變少。 既然如此，我們可以確定派$a$對戰$b$一定可以得到最佳解，並將$a$與$b$移除後，繼續依照上述原則挑選。 範例程式如下，因為要不斷的挑選最小值，而戰力不會改變，所以是個靜態的資料。我們可以將雙方戰力先進行一次排序，然後依序由小往大考慮即可。 ```python= # P_4_2, one-on-one O(nlogn), sorting+greedy n = int(input()) enemy = [int(x) for x in input().split()] ours = [int(x) for x in input().split()] enemy.sort() ours.sort() win = 0 # num of win ei = 0 # index of weakest enemy for p in ours: # each of our power if p > enemy[ei]: # can win some enemy win += 1 ei += 1 # next enemy # otherwise, p is useless, do nothing # print(win) ``` 這一題也可以由大到小考慮，基本原則是能贏的贏一點就好，當然可以用優先佇列(PQ)，在範例程式中有以PQ寫的方式，做法簡單，我們就不在此說明，有興趣練習PQ的可以自行參考。 --- ##### P-4-3. 十年磨一劍 (最少完成時間) 人們常用說「十年磨一劍」來比喻下的功夫深，但是這句話對於華山磨劍坊就不適用了，因為要磨劍的客人非常的多，一把劍如果磨太久，客人等待的時間過長是會被客訴的。華山磨劍坊目前有$n$筆訂單，每筆訂單要磨一把劍，每把劍所需的時間不盡相同。磨劍師傅每次只能磨一把劍，現在希望每一筆訂單的完成時間之總和能夠最小，希望能找出最好的磨劍順序。 舉例來說，如果有四把劍，磨劍需要的時間分別是(3,1,3,4)，如果以(3,1,3,4)的順序來磨，第一把的完成時間是3，第二把完成時間是3+1=4，第三把是3+1+3=7，第四把是3+1+3+4=11，總和是3+4+7+11=25。如果把順序改成(1,3,3,4)，那麼完成時間分別是(1,4,7,11)，總和是23，這是這一題最好的解。 Time limit: 1秒 輸入格式：第一行是一個正整數$n$，第二行有$n$個正整數是每一把劍需要的時間，同行數字間以空白間格。$n$與每把劍的時間都不超過1e5。 輸出：輸出最小的完成時間總和。 範例輸入： 4 3 1 3 4 範例結果： 23 --- 有$n$個工作要安排一個順序後依序完成，希望每個工作的完成時間總和最小，這是個經典的minimum completion time問題。直覺上短的工作要先做，放在越前面的工作，等它的人越多。如果把計算時間的方式仔細看一下，你會發現如果$job[i]$是第$i$個工作所需的時間，那麼完成總時間是 $\sum_{i=0}^{n-1} (n-i)\times job [i]$， 所以shortest-job-first是對的。另外一個證明方法是假設$job[i]$的順序是最佳解而存在某個工作$job[i]>job[i+1]$，那麼，我們交換這兩個相鄰工作，其他的工作的完成時間不會改變，但這兩個工作的完成時間總和會減少，如此可知，最佳解中不可能大的排在小的前面。這種考慮相鄰交換的情形是個證明的技巧，因為其它的工作不會改變，可以得到很簡單的證明。 程式非常簡單，排序後計算就好了，但是不要把計算寫成$O(n^2)$的笨方法了，運用prefix-sum的手法就很容易在排序後以$O(n)$完成計算，另外一個方法是用上面的公式。 ```python= # P_4_3, min completion time, sorting+greedy n = int(input()) job = [int(x) for x in input().split()] job.sort() # shortest job first curr = 0 # current completion time total = 0 # total completion time for t in job: curr += t # completion time of i total += curr # total completion time # print(total) ``` ### 多欄位資料排序 在上面兩個例題中，每個資料都只是一個數字，接下來我們要看需要資料具有多欄位(項目)的狀況。在第二章我們介紹排序時，說明過python中list與tuple是以字典順序比較大小，以及sort()中使用key的方法，如果不熟悉的人，請再次參考第二章的方法。 下面這一題是很有名的經典題 **Activity selection problem**。 --- ##### P-4-4. 幾場華山論劍 (activity selection) 自從華山論劍聲名大噪之後，想參加的人絡繹不絕，因此華山派決定每年都舉辦非常多場的華山論劍，每一場都有自己的開始時間與結束時間，參加者必須全程在場，所以不能在同一時間參加兩場。 令狐沖拿到了今年所有場次的資料，希望能參加越多場越好，以便盡速累積經驗值，請你幫忙計算最多可以參加幾場。請注意，所挑選活動必須完全不重疊，兩場活動只在端點重疊也是不可以同時參加的，也就是說**前一場的結束時間必須小於下一場的開始時間**。 Time limit: 2秒 輸入格式：第一行是一個正整數$n$，代表一共舉辦了$n$場華山論劍，接下來$n$行，每行兩個非負整數$s$與$t$，代表這場活動的時間區間是$[s,t]$，兩數字間以空白間格。$n$不超過1e5，$s < t < 1e9$。 輸出：最多參加幾場活動。 範例輸入： 4 1 4 0 3 3 4 4 6 範例結果： 2 說明：可以挑選[0,3]與[4,6]兩場活動。 --- 這個題目簡單說就是：數線上有若干線段，要挑選出最多的不重疊的線段。第一個想法可能是盡量挑短的，但是範例中有一個反例，挑短的不是正確答案。我們宣稱下面這個的性質： **「若$[x,y]$是所有現存線段中右端點最小的，那麼一定有個最佳解是挑選了$[x,y]$。」** 證明：假設最佳解沒有挑$[x,y]$，令$[a,b]$是最佳解中右端點最小的。根據我們的假設，$y \le b$，因此將$[x,y]$取代$[a,b]$不會重疊到任何最佳解中的其他線段，我們可以得到另外一個包含$[x,y]$的最佳解。 根據此性質，我們可以不斷地將最小右端的線段挑選進解答，然後略過任何與它重疊的線段。因為線段不會改變，一開始依照右端由小排到大，然後從頭到尾掃描一次就可以得到答案。 以下是範例程式，在此程式中我們用一個list $[start,finish]$來表示一個活動的起始與結束時間，排序時用 key=lambda x: x[1] 來定義排序的key值是一個元素$x$的第1個欄位$x[1]$，也就是結束時間，對排序lambda函數不熟悉的請複習第二章。 在排序後，以一個迴圈從頭到尾掃描一次，以變數endtime保持著前一個已挑選活動的結束時間，初值給 -1 因為輸入的時間皆為非負，迴圈內以if來判斷開始時間是否大於endtime，若是，挑選起來，修改答案與endtime；若否，可以直接丟棄它，不做任何事。 ```python= # P_4_4,activity selection, sorting+greedy n = int(input()) act = [] # [start,finish] for i in range(n): act.append([int(x) for x in input().split()]) act.sort(key=lambda x:x[1]) # sort by finish time endtime = -1 # last finished time total = 0 # num of selected activity for start,finish in act: if start > endtime: # compatible, select it total += 1 endtime = finish # else do nothing # print(total) ``` 如果因為不熟悉排序時下key的方式，可以將要比較的值放在每一個元素的第0個欄位，因為每個元素是list，兩個list比較時是先比第0個欄位的字典順序，所以會依照我們的需要的方式排序而省略寫key函數。在本題中，我們希望以右端點結束時間排序，我們就將右端點放在前面就行了。 以下是範例程式，大致上與前一支相同，在第6行讀入每一個活動的起始與結束時間時，我們以結束時間在前的順序放入$act$中，第8行排序時間就沒有給key了。留意在第11行歷遍時，每一筆資料取出的是finish,start，結束時間在前。 ```python= # P_4_4,activity selection, sorting+greedy # without key lambda n = int(input()) act = [] for i in range(n): s,t = [int(x) for x in input().split()] # [start,finish] act.append([t,s]) # finish at first act.sort() # sort by finish time endtime = -1 # last finished time total = 0 # num of selected activity for finish,start in act: if start > endtime: # compatible, select it total += 1 endtime = finish # else do nothing # print(total) ``` 本題中我們只需安排欄位的順序，但利用這個方式來避免寫key函數有的時候會多花記憶體，例如要比較的是幾個欄位運算的結果(例如下一題)，如果不下key，就變成要在每筆資料前方多開一個欄位，所以並非一定可行。 在P-4-3十年磨一劍的例題中，每一件磨劍工作，無論需要時間的長短，重要性都是一樣的，我們要求的只是完成時間的總和最小化，下面是一個變化題，每一個工作延後的代價不同。 --- ##### P-4-5. 嵩山磨劍坊的問題(加權最小完成時間) 嵩山磨劍坊接了$n$筆磨劍工作，磨劍師傅每次只能磨一把劍。除了每把劍各有所需的時間之外，每件工作的重要性也不同。假設第$i$筆訂單需要的時間是$t[i]$，而重要性是$w[i]$。磨劍坊的計價方式是：每件工作都已經先收了一筆款項，假設第$i$筆訂單在時間$f$時完成，則需要扣款$f\times w[i]$，現在希望將$n$筆磨劍工作安排最好的順序，使得扣款總額越小越好。嵩山派掌門左冷禪是非常嚴厲的老闆，希望你能幫磨劍師傅找出最好的順序以免他遭到處罰。 舉例來說，如果有四把劍，磨劍需要的時間分別是$t=(1,4,5,6)$，而重要性依序是$w=(1,3,4,7)$。如果依訂單編號順序$(1,2,3,4)$來磨，也剛好是工作時間由短到長的順序，每件工作的完成時間依序是$(1,5,10,16)$，扣款總額是$1\times 1 + 5\times 3 + 10\times 4 + 16\times 7 = 168$。如果依照訂單編號順序$(4,1,3,2)$ 來磨,則$t$與$w$重新排列後分別是$t=(6,1,5,4)$，$w=(7,1,4,3)$。完工時間是$(6,7,12,16)$，扣款總額是$6\times 7 + 7\times 1 + 12\times 4 + 16\times 3 = 145$。這是這一題24種排列中最好的解。 Time limit: 2秒 輸入格式：輸入的第一行工作數$N$，$N<1e5$。第二行有$N$個正整數，依序是各訂單所需時間$t[1],t[2],\ldots,t[N]$。第三行有$N$個非負整數，依序是各訂單的重要性$w[1],w[2],\ldots,w[N]$，時間與重要性皆不超過1000，相鄰以空白間隔。 輸出：輸出最小的扣款總額。答案不超過1e18。 範例輸入： 4 1 4 5 6 1 3 4 7 範例結果： 145 --- 如果每個工作(訂單)的重要性(w)都是一樣的話，這一題跟P-4-3就是一樣的，答案就是依照工作時間以Shortest-job first的方式排列，但是在有權重的狀況下，題目範例中就告訴你時間短的不一定在前面。我們再想想看，只看時間的話，時間短的應該排前面；那麼如果只看權重的話呢？權重大的應該排前面，因為延遲的話罰得重。但是兩個都要考慮的話，就必須兩個因子都列入考慮。 我們宣稱以下特性：**最佳解中，排在前面的，$t/w$值一定比較小**。證明？跟P-4-3類似，考慮排在相鄰的兩個工作，假設$t[i]/w[i] > t[i+1]/w[i+1]$。我們交換兩工作，其他的工作完成時間不會改變，而$i$延後了$t[i+1]$的時間，$i+1$則提早了$t[i]$的時間，因此變化量為$w[i]\times t[i+1] - w[i+1]\times t[i] < 0$，也就是解會變好。 程式的寫法不難，但是需要兩個欄位相除後的結果來排序。這裡要提醒，相除的結果是個浮點數，在類似的情形下也許有精準度的問題。以這一題的範圍，1~1000，不至於造成誤差。第二個問題，分母是否有可能是0？這一題是會。所以需要特殊處理一下，處理的方式是若$w=0$，則將key設為無窮大(本題1001就夠)，也可以先把$w=0$的都刪除，因為權重為0的沒有罰款，可以直接刪除。 ```python= # P_4_4,activity selection, sorting+greedy # without key lambda n = int(input()) t = [int(x) for x in input().split()] w = [int(x) for x in input().split()] job = [(x,y) for x,y in zip(t,w)] job.sort(key=lambda x: x[0]/x[1] if x[1] else 1001) # sort by t/w, if w==0, key=oo curr = 0 # current completion time total = 0 # total weighted completion time for t,w in job: curr += t # completion time of i total += curr*w # total completion time # print(total) ``` 下面一題很類似，因此留做習題，不多解釋。 --- ##### Q-4-6. 少林寺的自動寄物櫃 (APCS201710) 少林寺的自動寄物櫃系統存放物品時，是將$N$個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。 每一次升高貨架所需要消耗的能量是以這些物品的總重來計算。現在有$N$個物品，第$i$個物品的重量是$w(i)$而需要取用的次數為$f(i)$，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。 舉例來說，有兩個物品$w(1)=1$、$w(2)=2$、$f(1)=3$、$f(2)=4$，也就是說物品1的重量是1需取用3次，物品2的重量是2需取用4次。我們有兩個可能的擺放順序(由上而下)： * (1,2)，也就是物品1放在上方，2在下方。那麼，取用1的時候不需要能量，而每次取用2的能量消耗是$w(1)=1$，因為2需取用$f(2)=4$次，所以消耗能量數為$w(1)\times f(2)=4$。 * (2,1)。取用2的時候不需要能量，而每次取用1的能量消耗是$w(2)=2$，因為1需取用$f(1)=3$次，所以消耗能量數$=w(2)\times f(1)=6$。 在所有可能的兩種擺放順序中，最少的能量是4，所以答案是4。再舉一例，若有三物品而$w(1)=3,w(2)=4,w(3)=5$而$f(1)=1,f(2)=2,f(3)=3$。假設由上而下以$(3,2,1)$的順序，此時能量計算方式如下：取用物品3不需要能量，取用物品2消耗$w(3)\times f(2)=10$，取用物品1消耗$(w(3)+w(2))\times f(1)=9$，總計能量為19。如果以(1,2,3)的順序，則消耗能量為$3\times 2+(3+4)\times 3=27$。事實上，我們一共有3!=6種可能的擺放順序，其中順序(3,2,1)可以得到最小消耗能量19。 Time limit: 1秒 輸入格式：輸入的第一行是物品件數$N$，$N<1e5$。第二行有$N$個正整數，依序是各物品的重量$w(1),w(2),\ldots,w(N)$。第三行有$N$個正整數，依序是各物品的取用次數$f(1),f(2),\ldots,f(N)$，重量與次數皆不超過1000，相鄰以空白間隔。 輸出：輸出最小能量消耗值。答案不超過1e18。 範例輸入： 3 3 4 5 1 2 3 範例結果： 19 --- ### 以PQ處理動態資料(\*) 這一小節中我們提出需使用優先佇列(priority queue, PQ)的題目。由於APCS的範圍應該不包含PQ，所以照理說不太會出現在APCS考試中。 --- ##### P-4-7. 岳不群的併派問題(Two-way merge) (\*) 江湖上門派林立，華山派掌門岳不群認為要消除門派的衝突就是要合併各門派，但不能操之過急，必須每次挑兩個門派合併，如此逐步合併，最後將所有門派合併成一派。合併門派需要一些成本，每個門派都有他的成員數，第 i 個門派的成員數是 $m(i)$，合併兩派的成本就是雙方成員數之和，而兩派合併後，雙方成員就會歸到新合併的門派。岳不群不希望耗費太多成本，輸入各派人數，請幫他計算最少的合併總成本。 舉例來說，一開始如果有三派，$m=(3, 5, 1)$，若3人與5人的兩派先合併，成本是3+5=8，合併後剩下兩派，人數是(8,1)，再合併這兩派，成本是8+1=9，此時已經只剩下一派，也就是完成所有合併統一江湖了，總成本是8+9=17。如果我們更換合併的順序，先合併3人與1人的兩派(成本4)，再合併剩下的5人(成本4+5=9)，則總成本只有4+9=13。這是這個例子的最低成本。 Time limit: 2秒 輸入格式：第一行是一個正整數 $n$，代表初始的門派數量，第二行有 $n$ 個正整數是每派的成員數，同行數字間以空白間格。$n$ 不超過2e5，每個門派初始人數都不超過 1e5。 輸出：第一行輸出總人數，第二行輸出最小的合併總成本。 範例輸入： 3 3 5 1 範例結果： 9 13 --- 這一題事實上是Two-way merge tree的問題，與一個有名的Huffman code是等價的。正確的合併順序的計算方法是：每次挑選人數最少的兩派合併，重複此步驟直到剩下一派為止。任何一種合併的過程可以用一個二元樹表示，下圖是一個例子。 ![image](https://hackmd.io/_uploads/HyxvMhiUa.png) 圖中每個方塊表示一個初始的門派，圓圈表示一個合併。初始人數$m(i)$ 是 (7,2,3,5)，先合併 (2,3) 變成5，再合併(5,5) 變成10，最後合併 (7,10) 變成 17。合併的成本圓圈中的數字相加，這個例子 5+10+17=32 就是是最低成本。這一題的證明稍嫌麻煩，我們在此不給完整的證明，只做一些說明。總成本也可用另外一個方式計算，每一個方塊往上走到頂會經過幾次圓圈(稱為深度)，就代表他經過幾次合併，所以每個 $m(i)$ 乘上他的深度加總後就是總成本，所以直覺上看得出來，數字越大的要放在深度小的地方，也就是說數字越小的要越早合併，完整的證明留給讀者上網搜尋Huffman code或two-way merge tree。 雖然證明有點麻煩，但是程式非常好寫，我們只要每次找出最小的兩個數，將他們刪除，再將他們的和放入。重複這個步驟直到剩下一個數字。但是要有效率的做到必須借助資料結構，如果使用排序，每次刪除最小值或許不是大問題(記住有效位置，每次後移兩格就好)，但是插入兩數相加的和就會很浪費時間了。以下是用陣列的方法寫的範例程式，時間複雜度是 $O(n^2)$。雖然他效率不夠好，但是我們也使用了一些技巧來減少資料搬移的動作，所以也算個好的練習。 我們維持list $m$永遠是排好序的狀態，每次要找最小的兩個元素把它們移除後，再將他們相加後的和插入 $m$ 中並保持排好序的狀態。插入排序好的list可以用bisect中的insort，或是bisect_left加上insert，但必須是上升遞增；要移除方便，最好刪除的是在尾端。因此我們用負值放入進行遞增排序，這樣是原始資料的遞減排序。每次從尾端pop兩個資料就是最小的兩個。但是insort還是$O(n)$，所以整體時間還是$O(n^2)$。 ```python= # P_4_7 greedy, slow n^2 method using array import bisect n = int(input()) m = [-int(x) for x in input().split()] # negative m.sort() # origibal val large to small total = 0 # total cost for i in range(n-1): # merge n-1 times cost = m.pop() # smallest cost += m.pop() # second smallest total += cost # insert into increasing list bisect.insort(m, cost) # print(-m[0]) print(-total) ``` 要能夠有效率的做到增刪資料，我們必須借助資料結構，優先佇列每次可以找到最小值，是這一題最適合的資料結構，只要每次pop出兩個資料，相加後push回去就可以了。 ```python= # P_4_7 greedy, O(nlogn) using pq import heapq n = int(input()) m = [int(x) for x in input().split()] heapq.heapify(m) # heap initialization total = 0 # total cost for i in range(n-1): # merge n-1 times cost = heapq.heappop(m) # smallest cost += heapq.heappop(m) # second smallest total += cost # insert into heap heapq.heappush(m,cost) # print(m[0]) print(total) ``` 下面一個題目是在工作排程時的問題，做法簡單，但證明需要想一下，留做習題，如果資料量不大，可以用陣列做，但資料量大時，必須使用資料結構。 --- ##### Q-4-8. 先到先服務 (\*) 有 $n$ 個客人要分配到 $m$ 個櫃台來服務，客人依編號順序到達，第 $i$ 個客人需要 $t(i)$ 的時間來完成(無論分配到哪一個櫃台)，而且同一位客人的需求必須在同一個櫃台完成，不能分拆。因為公平的因素，**先到客人不可以比晚到客人更晚開始服務**。現在希望安排每個客人的服務櫃檯，以便可以在最短的時間內完成所有客人的需求。 舉例來說，如果有三位客人與兩個櫃台，需求的時間依序是(3,1,5)，我們可以如下分配，最後的完成時間是6。 櫃台1：3 櫃台2：1+5 請注意，我們不可以如下分配，雖然這樣的完成時間會減少到5，但是第3個客人(5)比第2個客人(1)早開始服務，違反了先到先服務的原則。 櫃台1：3+1 櫃台2：5 Time limit: 2秒 輸入格式：輸入兩行，第一行是正整數 $n$ 與 $m$，第二行是 $n$ 個正整數$t(1), t(2),\ldots ,t(n)$，同行數字間以空白間格。$n$ 與 $m$ 不超過2e5，$t(i)$ 不超過1e4。 輸出：最早可能服務完所有客人的時間。 範例輸入： 3 2 3 1 5 範例結果： 6 --- **End of Chapter 4 (I)** 下接 [AP325-Python 第4章 貪心演算法與掃瞄線演算法 (II)](/mEi9wqzjRCuj2aixy3Ea2Q)