Introduction

假設你在中友百貨 15 樓 A 棟，你想去 1 樓搭公車，好巧不巧，電梯壞了，你會怎麼做？
一般人都是搭手扶梯吧。

但在這有兩個前提，首先你必須確定方向無誤，搭的是往下的手扶梯，並且，你假設每層樓 A 棟手扶梯與通往 B 棟的通道不會同時阻塞，否則你必須往上再從其他棟往下。

貪心就像這個過程，首先你在一個不知名的地方，想走到目的地(最佳解答)，你一直做某些不會讓情況變差的事(往下)，並且確定一定會走到那裡。

再舉個例子，你想拿最少紙鈔和硬幣來付錢，肯定從面額大的找。

貪心是一個很玄的領域，解法天馬行空，證明複雜難懂，幸好還是有一些經典題。

排序不等式

直接上例題
題目叫你排東西，但是長度 n 就有 n! 種排法，怎麼辦呢？
排序不等式經常是從相鄰的比較開始，先觀察兩個物品的情況。
如果物品1在物品2前面比較好，代表總能量要比排在後的總能量小，否則，應交換它們的位置。
也就是說，我們希望下面式子成立。

w1*f1+(w1+w2)*f2 <= w2*f2+(w1+w2)*f1
w1*f2 <= w2*f1
w1/f1 <= w2/f2

如果不只兩個物品呢？其實像下面兩種排列，對 1 來說 2,3 都在後，對 4 來說 2,3 都在前，拿 1,4 使用的能量不變。

1 2 3 4
1 3 2 4

因此只要確定所有 w[i]/f[i] <= w[i+1]/f[i+1]，也就是以 w[i]/f[i] 將物品排序，就能拿到最好的答案。

題目特徵

1. 每個位置上的數字依順序對答案貢獻
2. 相鄰數字順序好壞可用一個式子 f(i)<=f(i+1) 表示
3. f(i) 只能用位置 i 的資料和常數，像上面例子中 f(i)=w[i]/f[i]
4. <= 必須滿足遞移律(能排序)

其他題目

• USACO Greedy-Sorting
• Codeforces 1552B (不滿足遞移律的例子）