10/23 preTraining
題意 : 給整數 \(n\) 代表 \(n\) 個數字,從 \(n\) 個數字中,不斷選出兩個數字相加,並將數字和加到cost 裡,並將相加後的數字丟回數字堆中,求最後剩下一個數字時的最小 cost
解法 : 解法應該很直觀,就是每輪不斷地從中選出兩個最小的數字相加,直到最後剩下一個數字
由於每輪都是選當前最佳選項(讓當次操作成本最低),而且一直做下去就是最佳解,因此本題為 greedy 題,證明則是可以思考一下他的加法總和,只需要把所有東西都列出來即可。
這題實作上是用 priority_queue,一開始把所有東西丟進去,每次把最小的兩個取出來,相加加進成本並把結果丟回 priority_queue,直到只剩一個數字
複雜度 \(O(n \log n)\) (priority_queue)
題意 : 現在有一些題目,已知每題的所需時間,排列出解題順序使得總penalty最小,一個題目的 penalty 計算方式從一開始到解完該題的時間總和,也就是前面解的題目 + 當前題目的時間總和(時間是一直在走的)
解法 : 很直觀的作法就是由快而慢寫,也就是直接由小排到大(證明可以自己想想看,也是使用反證法)
因此一開始 sort 完然後好好計算 penalty 即可
由於 penalty 的算法就是很直接地加上去,因此先解決最快可解決的題目會讓後面的題目更快被解決使得 penalty 最小,而一直選擇最小數字就是最佳解,因此此題為 greedy 題,證明與上一題 add all 類似。
Greedy 通常分為兩種
通常難在"如何想到並證明一個好的偏序關係(排序方式)",找到偏序關係後通常就直接照著此偏序關係排序,然後剩下就好好做完就好,例如例題 NPSC筆電自動機 以及去年 ICPC Taoyuan site pF
一般而言會從 \(n = 2\) 時開始考慮,當只有 2 個物件時的比較方法,再推廣到多個物件(但須判斷是否符合偏序關係)
也就是去思考每個 case 對於答案的貢獻以及對於前後者的影響,考慮清楚之後 greedy 的式子就會浮現在腦中
給定 \(n\) 條線段 (\(l_i\) ∼ \(r_i\)),選出盡量多條線段,其中這些線段不得重疊。
以下有幾種狀況(排序方法)來決定 greedy 選擇線段的順序:
請問哪一個是對呢 :)
實際操作只需要排序後就 greedy 選取即可(若當前線段與已選線段重疊則捨棄,反之則選取)
狀況1的反例
3
1 5
2 3
4 5
狀況3的反例
3
1 5
4 7
6 10
至於狀況 4 以及 5 根本就是在唬爛。
有 \(n\) 份工作,每份工作有所需時間 \(t_i\) 與期限 \(d_i\),求是否能找到一個工作順序使得可以在期限內完成所有工作。
直觀的想法:
這邊給出 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 策略是好的
有 \(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]\) 作為比較方法(排序的偏序關係)
有 \(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\) 個
因此接下來考慮應該
捨棄第 \(i\) 個工作
選擇做第 \(i\) 個工作,並移除前面選的某一項工作
已知為了後面好,在同樣只能完成 \(k\) 個工作的情況下,應該要盡量減少總工作時間,因此移除這 \(k+1\) 個工作中工時最長的工作是最好的選擇(前提是剩餘 \(k\) 個工作皆能完成,但根據我們的假設,這並沒問題)
再來是證明移除這 \(k+1\) 個工作中工時最長的,
剩下 \(k\) 個工作必能準時完成
得證,移除第 \(a_j\) 項工作後,第 \(i\) 項工作可以準時完成 \(\Rightarrow\) 剩下的 \(k\) 個工作皆能準時完成
因此實作上就是用個 priority_queue 去維護前面已選的工作的工時,依序考慮每一個工作,如果加入該工作可以準時完成則直接加入,反之則加入後並移除其中工時最長的工作,做到最後 priority_queue 的大小即為所求(此外 priority_queue 內數字總和是在滿足最大化準時完工數量的條件下,最短的總工時)
這種類型的的題目也叫做反悔 greedy,在過程中先選起來當前最佳
之後遇到更好的就反悔選更好的。