<style> .reveal .slides { text-align: left; font-size:35px } </style> # Greedy Introduction to Competitive Programming 2/6 ---- * 核心概念及前言 * 經典例題(上課用到簡單ㄉ) * 實作方法及想法 * 經典例題(就很經典) --- ## 前言 --- greedy是甚麼鬼? * 貪婪，也就是跟政府官員一樣，有的拿就拿，有的做就做 * 像 DP(動態規劃) 或 DC(分治) 一樣都是用小問題歸納大問題 * 可以 greedy 的題目都相對容易實作，但是要證明 greedy 是正確的並不容易，所以課程內容大部份為數學證明 * 在賽中容易想到一種 greedy 解，請仔細考慮是否正確在實行，通常反例不難求 * 能greedy的題目大部分都可以 DP 解，但還是要考慮時間、空間複雜度 ---- ## 核心概念-greedy的必知知識 * 題目屬於最佳化問題，也就是你使用某一種策略，總是可以獲得最好的結果 * 假設一個問題可以分成很多步驟，那麼每一輪(次)都選擇當前最好的那一個 * 或者如果問題是要排列東西使得最大/小化某個目標函數，那麼可以找到一種比較函數(偏序關係)，用它排序後即為正解 --- 簡單範例題 [Add All](https://zerojudge.tw/ShowProblem?problemid=b606) 題意 : 給 $n$ 以及 $n$ 個數字，從 $n$ 個數字中，不斷選出兩個數字相加，cost 為其總和，並將相加後的數字丟回數字堆中，求最後剩下一個數字時的最小 cost 解法 : 解法應該很直觀，就是每輪不斷地從中選出兩個**最小**的數字相加，直到最後剩下一個數字 ---- 由於每輪都是選當前最佳選項(讓當次操作成本最低)，而且一直做下去就是最佳解，因此本題為greedy題，證明則是可以思考一下他的加法總和，用反證法。 這題實作上是用 priority_queue，一開始把所有東西丟進去，每次把最小的兩個取出來，相加加進成本並把結果丟回 priority_queue，直到只剩一個數字 複雜度 $O(n \log n)$ (priority_queue) ---- 簡單範例題 [NPSC筆電自動機](http://203.64.191.163/ShowProblem?problemid=a071) 題意 : 現在有一些題目，已知每題的所需時間，排列出解題順序使得總penalty最小，一個題目的penalty計算方式從一開始到解完該題的時間總和，也就是前面解的題目+當前題目的時間總和(時間是一直在走的) 解法 : 很直觀的作法就是由快而慢寫，也就是直接由小排到大(證明可以自己想想看，也是使用反證法) 因此一開始sort完然後好好計算 penalty 即可 ---- 由於penalty的算法就是很直接地加上去，因此先解決最快可解決的題目會讓後面的題目更快被解決使得penalty最小，而一直選擇最小數字就是最佳解，因此此題為greedy題，證明與上一題add ALL類似。 --- # 實作方法 Greedy 通常分為兩種，分別為步驟類型(動態、靜態)以及排序類型。 ---- ## 對於分步驟類型題目 * 通常分成"靜態"與"動態"兩種，是對於原本的資料是否有修改。 * 其中靜態指的是每輪操作後，原資料不會再被修改，所以可以直接排序一次過後做到底。而動態則是每輪操作後會有修改，例如例題Add All * 對於靜態的題目，通常一開始用指定方法sort完後由前做到後即可 * 對於動態的題目，通常需要用priority_queue，一開始把所有東西丟進去，之後每輪取最佳解出來並做修改(再丟東西進priority_queue之類的) ---- ## 對於靜態的，排列類型的題目 通常難在"如何想到並證明一個好的偏序關係(排序方式)"，找到偏序關係後通常就直接照著此偏序關係排序，然後剩下就好好做完就好，例如例題NPSC筆電自動機 ---- ## 如何構造比較方法? 一般而言會從 $n$ = 2 時開始考慮，當只有 2 個物件時的比較方法，再推廣到多個物件(但須判斷是否符合偏序關係) --- # 下課時間 --- ## 經典題目時間 * * * * ---- ## Q1 : [最大線段互斥集](http://203.64.191.163/ShowProblem?problemid=a076) 給定$n$條線段($l_i$ ∼ $r_i$)，選出盡量多條線段，其中這些線段不得重疊。 以下有幾種狀況(排序方法)來決定greedy選擇線段的順序: 1. l 由小排到大 2. r 由小排到大 3. r - l (長度) 由小排到大 4. l + r (index) 從小排到大 5. r - l (長度) 從大排到小 請問哪一個是對呢 :) ---- 實際操作只需要排序後就greedy選取即可(若當前線段與已選線段重疊則捨棄，反之則選取) 狀況1的反例 ```cpp 3 1 5 2 3 4 5 ``` 狀況3的反例 ```cpp 3 1 5 4 7 6 10 ``` 至於狀況 4 以及 5 根本就是在唬爛。 ---- ## Q2 : [單機排程問題](http://203.64.191.163/ShowProblem?problemid=a078) 有$n$份工作，每份工作有所需時間$t_i$與期限$d_i$，求是否能找到一個工作順序使得可以在期限內完成所有工作。 直觀的想法: 1. 先做時間短的，也就是排序 $t_i$ 2. 先做期限近的，也就是排序 $d_i$. 3. 根據他們的最晚開始時間排序，也就是排序 $d_i - t_i$ 4. 感覺不是 greedy 很像 DP 又是哪一個選項呢(歪頭笑 :face_with_hand_over_mouth: ---- 這邊給出 1 和 3 的反例 : ```CPP 2 2 1 3 ``` 並且提供 2 的證明。首先，先假設有一組是能如期完成所有工作的排序 arr ，並對所有 arr 有一 $i$ ( $1$ $\le$ $i$ $<$ $n$ ) ，且$d_i$ $>$ $d_{i+1}$. 對於一個能如期完成所有工作的arr，會有$s_{1...j}$ ($\sum_{i=1}^{j}\limits {t_i}$) $\le$ $d_j$ , $∀$$j$ 交換第 $i$ 與 $i+1$ 項只會對 $d_i$ , $d_{i+1}$ , $s_i$ 造成影響由於 $s^′_{0...i+1}$ = $s_{0...i+1}$ $\leq$ $d_{i+1}$ $<$ $d_i$ = $d^′_{i+1}$ 因此新的第 $i+1$ 項是可以準時完成，且整體更優於原方案的偏序. 其餘項 $s$,$d$ 皆無影響因此皆能準時完成 ---- 因此得證，若存在排列能如期完成所有工作，但有相鄰項違反 $d_i$ $<$ $d_{i+1}$，那麼將兩項交換必然也能如期完成所有工作⇒照著 $d$ 由小排到大必然能如期完成所有工作⇒此greedy 策略是好的 ---- ## Q3 [APCS 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471) 有 $n$ 個物品，每個物品有重量 $w_i$ 和取用次數 $f_i$ ，現在要將物品由上而下排列，取用一項物品的成本為其上方所有物品重量總和，求最低成本為何。 解法: 首先假設物品由上而下依照 $i$排列，那麼可以列出成本式子 $\sum_{i=0}^{n-1}\limits f_is_i$ 其中 $s_i$ = $\sum_{j=0}^{i-1}\limits w_j$是物品重量的前綴和 ---- 考慮只有兩項物品 ( $i$ , $j$ ) 時的排列方法: $i$ 在 $j$ 上方的成本為: $f_i$ $\cdot$ $0$ + $f_j$ $\cdot$ $w_i$ = $f_j$ $\cdot$ $w_i$ $j$ 在 $i$ 上方的成本為: $f_j$ $\cdot$ $0$ + $f_i$ $\cdot$ $w_j$ = $f_i$ $\cdot$ $w_j$ 將兩者比大小即可決定誰在上誰在下 ---- 接下來考慮將相鄰項交換對其他項成本的影響: $f_i$ 必不會改變，上下方的 $s_i$ 也不會改變，因此交換相鄰項只會影響此兩項的成本，其他項皆不受影響 ⇒不斷比較相鄰項交換是否會比較好 ⇒最終狀態等同是用 $f[j]*w[i]<f[i]*w[j]$ 作為比較方法(排序的偏序關西) ---- ## Q4 [單機排程問題 進階版](http://203.64.191.163/ShowProblem?problemid=a081) 有 $n$ 份工作，每份工作有所需時間 $t_i$ 與期限 $d_i$，最多能準時完成多少份工作?(其餘工作可以捨棄不做) 從 Q2 的證明可以得知，假設決定好要選做哪些工作，那麼將 $d$ 由小排到大就能確認是否能全部準時完成 因此一開始就先將所有工作按照 $d$ 由小排到大，剩下就只需要考慮要選哪些工作而已 ---- 假設前 $0\sim i−1$ 項中最多只能準時完成 $k$ 個工作，且其中一組最佳解是做 $a_1$ , $a_2$,...,$a_k$ 這 $k$ 個工作(此 $k$ 個工作皆能準時完成)，現在考慮第 $i$ 個工作(欲求前 $i$ 項工作最多能準時完成多少個): 若直接將第 $i$ 個工作加進去能準時完成(也就是 $\sum_{j=1}^{k}\limits t_{a_j}+t_i \le d_i$) 那麼就將它加進去，因此前 $i$ 項工作最多能準時完成 $k+1$ 個 反之代表前 $i$ 項工作最多只能完成 $k$ 個 ---- 因此接下來考慮應該 1. 捨棄第 $i$ 個工作 2. 選擇做第 $i$ 個工作，並移除前面選的某一項工作 已知為了後面好，在同樣只能完成 $k$ 個工作的情況下，應該要盡量減少總工作時間，因此移除這 $k+1$ 個工作中工時最長的工作是最好的選擇(前提是剩餘 $k$ 個工作皆能完成，但根據我們的假設，這並沒問題) ---- 再來是證明移除這 $k+1$ 個工作中工時最長的， 剩下 $k$ 個工作必能準時完成 1. 如果工時最長的是 $i$，很明顯捨棄 $i$ 可以符合條件 2. 反之假設移除了 $a_j$ 這項工作，已知那 $k-1$ 項工作必能準時完成(原本$k$項都能準時完成了，工作減少一定也能準時完成)，因此只須考慮第 $i$ 個工作 由於前 $k$ 項皆能準時完成: $\sum\limits_{j=1}^{k}t_{a_j}\le d_k且d_k\le d_i$與$t_i\le t_{a_j}$ $\Rightarrow\sum\limits_{j=1}^{k}t_{a_j}-t_{a_j}+t_i\le\sum\limits_{j=1}^{k}t_{a_j}\le d_k\le d_i$ ---- 得證，移除第 $a_j$ 項工作後，第 $i$ 項工作可以準時完成$\Rightarrow$剩下的 $k$ 個工作皆能準時完成 因此實作上就是用個 priority_queue 去維護前面已選的工作的工時，依序考慮每一個工作，如果加入該工作可以準時完成則直接加入，反之則加入後並移除其中工時最長的工作，做到最後 priority_queue 的大小即為所求(此外 priority_queue 內數字總和是在滿足最大化準時完工數量的條件下，最短的總工時)