# 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$。

---

因為代幣的數量希望要最少，直覺貪心的想法就是要盡量使用面額大的硬幣，代幣由大面額的往小的考慮，能換盡量換，剩下不足的再考慮比較小的面額。以下是這樣的程式。

# 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的正負號。以下的範例程式介紹基本用法，說明請見程式內註解。

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$移除後，繼續依照上述原則挑選。

範例程式如下，因為要不斷的挑選最小值，而戰力不會改變，所以是個靜態的資料。我們可以將雙方戰力先進行一次排序，然後依序由小往大考慮即可。

# 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)$完成計算，另外一個方法是用上面的公式。

# 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；若否，可以直接丟棄它，不做任何事。

# 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，結束時間在前。

# 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的沒有罰款，可以直接刪除。

# 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是等價的。正確的合併順序的計算方法是：每次挑選人數最少的兩派合併，重複此步驟直到剩下一派為止。任何一種合併的過程可以用一個二元樹表示，下圖是一個例子。


圖中每個方塊表示一個初始的門派，圓圈表示一個合併。初始人數$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)$。

# 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回去就可以了。

# 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)