---
type: slide

slideOptions:
transition: fade;

---

<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>

# 貪心
## Greedy

10/23 preTraining

----

* 核心概念及前言
* 經典例題
* 實作方法及想法
* 經典例題

---

## 前言 --- 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筆電自動機](http://203.64.191.163/ShowProblem?problemid=a071) 以及去年 [ICPC Taoyuan site pF](https://icpc2023.ntub.edu.tw/wp-content/uploads/2023/10/ICPC2023-ProblemSet-Hint.pdf)

----

## 如何構造比較方法?

一般而言會從 $n = 2$ 時開始考慮，當只有 2 個物件時的比較方法，再推廣到多個物件(但須判斷是否符合偏序關係)

也就是去思考每個 case 對於答案的貢獻以及對於前後者的影響，考慮清楚之後 greedy 的式子就會浮現在腦中

---

## 經典題目時間

* 最大線段互斥集
* 單機排程問題
* APCS 物品堆疊
* 單機排程問題 plus

----

## 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的反例

3
1 5
2 3
4 5

狀況3的反例

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 的反例 :

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}$，那麼將兩項交換必然也能如期完成所有工作 $\to$ 照著 $d$ 由小排到大必然能如期完成所有工作 $\to$ 此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$ 也不會改變，因此交換相鄰項只會影響此兩項的成本，其他項皆不受影響

$\to$ 不斷比較相鄰項交換是否會比較好
$\to$ 最終狀態等同是用 $f[j]\cdot w[i]<f[i]\cdot 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 內數字總和是在滿足最大化準時完工數量的條件下，最短的總工時)

這種類型的的題目也叫做反悔 greedy，在過程中先選起來當前最佳
之後遇到更好的就反悔選更好的。