貪心法則 (greedy method)

所謂貪心法呢，就如字面上的意思一樣，”每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇” (維基百科)。例如: 每次都選價值最高的，每次都選最便宜的，或是每次都選最早開始的。貪心法呢雖然概念非常簡單，但是要非常注意的一點是，貪心法有可能不是最佳解。因此，貪心法雖然有時候非常直覺，但是要證明他的正確性是比較難且很重要的。

讓我們來看看一個生活中常見的例子，換零錢。假如今天店員要找我 887 塊錢，他該怎麼找才可以讓所用的硬幣 / 鈔票數量總共最少?

我們可以很直覺的想到，我們可以每次都找不超過的最大面額，所以店員可以先用 500，再用 3 個 100，一個 50 ….
而這個想法是對的! 也就是貪心法的一個應用，每次都選可以用的 最大的。用邏輯證明的話，我們可以發現，用一張 500 可以代替五張 100，用一張 100 可以代替 2 個 50，所以這樣選一定是最少的。

但是，如果今天某個國家的紙幣面額很奇怪，只有 50, 28, 10, 1。如果店員要找我 56 塊，先從 50 塊拿就不是最好的了。我們拿 2 個 58 會比 1 * 50 + 6 * 1 而少上許多。

在寫貪心法的時候，可能你可以通過很多測資，但是也可能會存在所謂的反例，要特別注意。資訊之芽的講義裡面有提到如何證明貪心法是最優解，非常建議大家去看看!

接下來我們帶一個例題看看: CSES Movie Festival

既然都說了這題是 Greedy，那你可能會想到一些 greedy 的方法。但是，有很多都是錯的，例如：

選最早開始的電影

選最短的電影

這題要每次都貪心的選取結束時間最早的電影來看我們才可以得到最好的結果。
每次都選結束最早的電影的話，就可以最大化我們之後可以選的電影的範圍 (因為結束比較早)。
這個greedy詳細證明的部分在吳邦一教授的 AP325 (4.2.2)單元中有提到。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <pair<int,int> > a(n);
    //first = 右 second = 左
    for(int i = 0;i < n;i++){
        cin >> a[i].second >> a[i].first;
    }
    
    sort(a.begin(), a.end());
    int cur = 0;
    long long ans = 0;
    for(int i = 0;i < n;i++){
        if(a[i].second >= cur){
           cur = a[i].first;
           ans++;
        }
    }
    cout << ans << '\n';
}

其實 greedy 有非常多的應用，像是我們之前學的 kruskal 最小生成樹就是一種 greedy 的想法。通常 greedy 很容易寫，只是要證明他的正確性是非常重要的 ! 尤其是在 APCS 這種沒辦法即時得知結果的考試，要好好的思考這樣到底會不會是對的 !