---

Greedy 貪心演算法
===


## 前言

恭喜各位在程設班活過第一週，這節上的是貪心
上課會變成簡單介紹後開始教例題
(這就是貪心的練習方式，他挺玄的)
只講貪心的話想法可以套在大多題目上面
也算是為未來的分治或 `dp` 做個練習
然後因為我們是 `apcs` 導向
基本上在 `apcs` 做貪心也很冒險
所以也會教各位如何簡單證明
以及 `apcs` 後測重要的對拍

## 基本介紹
### 所以貪心是什麼


想像一下你現在可以在一週內任選一天請假在家耍廢，在不考慮每天的課程內容的時候你會想優先請哪天?
肯定是要留8:50晚自習的其中一天||不要請程設班 歐內該||
又或者是你們今天一大群人出門吃飯但要趕時間，同時餐點是一份一份分開出的，那要讓誰先吃飯?
那肯定是吃最慢的那個
這些基本上會是生活也常見的貪心問題，相信各位都能很直覺的想出他們的解
如果要把貪心講的比較認真的話，那他就是在每一步做出當下看起來最有利（局部最優）的選擇，希望累積成全局最優

---
### 小例題
#### 換硬幣
有個國家的硬幣面額是[1,5,10]，問 `x` 元換成硬幣最少需要拿多少個硬幣

照著前面提到的貪心想法，可以直覺的想到從最大的開始往下減掉金額。
不過凡是遇到這種貪心問題，再直覺都一律建議要證明一下，尤其在 `apcs` 是後測，不能像一般競賽丟出去試試看，那你可能會想問到底該怎麼證明，沒事這就是等等會教的。

## 證明
### 找反例
最直覺 最快 同時也是最不嚴謹的證明法，基本上就是人腦去想有沒有反例，一樣拿這題來講，至少我腦袋想不出反例。
有的人到這布發現沒反例就會很開心地開始寫了，但需要非常非常注意
大多數的貪心假解都很難找到反例，所以我們需要更嚴謹的證明方法

### 交換論證（Exchange Argument）：偷偷把別人的最佳解變成我的形狀

這是證明貪心最經典、也最強大的一招。他的想法很酷，大概可以濃縮成三句話：
1. 首先，我們假設存在一個「絕對的最佳解」，但這個解法的第一步跟我們貪心策略「不一樣」。
2. 然後，我們動手「交換」一下，把絕對的最佳解的第一步，改成我們貪心的選擇。並且證明，這樣一換，結果「不會變差」（可能一樣好，甚至更好）。
3. 既然每一步都能這樣換，那我們就能一路把「絕對的最佳解」換到跟我們的「貪心解」一模一樣。結論：我們的貪心解，就是最佳解

我們用 `[1, 5, 10]` 換硬幣的例子來實際操作一次（注意：這個證明只對這組面額有效）：

- **第一步：思考硬幣結構**
- 如果你的最佳解裡面有 `5` 個以上的 `1` 元硬幣，我是不是可以把它們換成 `1` 個 `5` 元硬幣？硬幣總數就會從 `5` 個變成 `1` 個，少了 `4` 個，答案變得更好了，所以，一個「真正最優」的解，`1` 元硬幣的數量絕對不會超過 `4` 個。
- 同理，如果你的最佳解裡面有 `2` 個 `5` 元硬幣，我總能把它們換成 `1` 個 `10` 元硬幣。硬幣總數從 `2` 個變 `1` 個，又更好了！
所以，`5` 元硬幣的數量只可能是 `0` 或 `1` 個。


- **第二步：得出結論**
- 綜合以上，任何一個最優解的樣貌，一定是：「盡可能多的 `10` 元，加上最多一個 `5` 元，最後加上 `0` 到 `4` 個 `1` 元」。
- 嗯？這個結構不就跟我們「從大面額開始拿」的貪心策略，結果完全一樣嗎？
- 那就對了！證明完畢。我們的貪心是對的。

白話總結這個證明：「對於 `[1, 5, 10]` 這組面額，每一步只要能換成更大的硬幣，永遠不虧。」

---

### 反例

看了上面的證明，你可能會覺得貪心很穩很強。
但不過，很多的貪心假解也都很容易直接發現反例。

**狀況一：** 面額是 `[1, 3, 4]`，要湊 `6` 元。
- **貪心解**：先拿 `4` 元，還差 `2` 元。再拿 `1` 元，再拿 `1` 元。總共 `3` 枚硬幣。
- **最優解**：拿 `3` 元，再拿 `3` 元。總共 `2` 枚硬幣。
- 蛤? 貪心解不是最好的。

**狀況二：** 面額是 `[1, 5, 10, 20, 25]`（美金硬幣），要湊 `40` 分。
- **貪心解**：先拿 `25`，還差 `15`。再拿 `10`，還差 `5`。再拿 `5`。總共 `3` 枚。
- **最優解**：拿 `20`，再拿 `20`。總共 `2` 枚。
- 又爆了！

所以請務必在心裡記下這句話：**想用貪心，請先證明。找不到反例，不代表它就是對的。** 不然就會像某人在 `YTP` 線下賽拿著貪心對 `DP` 水題特判了一小時才發現自己在耍白癡

---

### Stays-ahead（一路領先）證明：

白話:我每一步都比你強

這是另一種很常見的證明方法，適合用在「需要先排序，再一步步做選擇」的問題上。經典的例子就是「活動選擇問題 (Interval Scheduling)」。

**問題描述：** 教授給你一大堆活動的清單，每個活動都有開始時間 `s_i` 和結束時間 `f_i`。你同一時間只能參加一個活動，請問你最多可以參加幾個活動？

**貪心策略：** 把所有活動依照「結束時間」由早到晚排序。然後從頭開始掃描，只要一個活動跟已經選的活動不衝突，就可以直接選它！

**證明想法（一路領先法）：**
- 我們把貪心策略選出來的活動清單叫做 `G` (Greedy)。
- 再假設有一個最佳解，叫做 `O` (Optimal)。
- 我們可以證明一個很酷的性質：「對於任何數字 `k`，`G` 中選到的第 `k` 個活動，它的結束時間，一定『不會晚於』`O` 中選到的第 `k` 個活動的結束時間。」
- 想像一下，這就像兩個人在比賽，我們的貪心選手 `G` 在每一步都跟最佳選手 `O` 一樣快，甚至還稍微領先一點點（更早結束）。
- 既然每一步都不落後，跑到終點時，我們選的活動數量，自然也就不會比 `O` 少。因此，我們的貪心解 `G` 就是一個最優解。
這種證明的關鍵，在於找到一個可以比較的「進度指標」（在這個例子裡，就是「已選的第 `k` 個活動結束得有多早」），然後用數學歸納法把它串起來，證明我們「一路領先」。


---

### 最佳子結構 vs. 貪心選擇性：DP 和貪心的差異

我知道上面兩個神奇的名詞看起來很可怕，我也知道你們還沒學 `DP` ，但還是得學一下這技巧有助於你日後判斷題目該用貪心還是 `DP`。

- **最佳子結構 (Optimal Substructure)：** 這個東西說的是，一個大問題的最優解，可以由他的小部分（子問題）的最優解組合而成。這是 DP 和貪心都會有的共同特徵。
- **貪心選擇性 (Greedy-choice Property)：** 這個性質就更酷了。他說的是，在做決策的當下，存在一個「局部最佳選擇」，你做了這個選擇後，並不會害你錯失通往「全局最優解」的任何機會。這個性質很強，但也很難證明。

簡單來說：
- 如果一個問題只有「最佳子結構」，但你找不到那個「做了不後悔」的貪心選擇，那這題通常要用 DP 來全面地考慮所有子問題。
- 如果它既有「最佳子結構」，又能被你證明有「貪心選擇性」，恭喜你，這題可以用更簡單、更快速的貪心法（通常是排序後一次掃描）來寫:D

再白話點說就是：即使發現了最佳子結構不代表一定是貪心，必須要再找到貪心選擇性才能完全確保他的最佳解會是貪心

---

## 實作流程


當你懷疑一題可以用貪心時，可以試著照下面這個 SOP 走一遍：

1. **定義你的選擇：** 先想清楚，在問題的每一步，你要做什麼決定？是「選」哪個東西？「刪掉」哪個東西？還是「合併」哪兩個東西？
2. **提出貪心規則：** 接著，大膽的猜一個貪心規則(反正都貪心夠大膽了，這麼再大膽一下問題不大），這個規則通常跟「排序」有關。例如：最早結束的優先、處理時間最短的優先、CP 值（權重/成本）最高的優先、數值最大的優先等等
3. **寫出證明草圖：** 嘗試用前面教的證明方法（交換論證、一路領先、找反例）在腦中或紙上快速推演一下。你不需要寫出一定正確的的嚴謹證明，但至少要能說服你自己，告訴自己為什麼這個規則在各種情況下都會是最佳解不會出現更好的解法。
4. **處理邊界與 Tie-breaking：** 思考一些極端狀況。如果好幾個選項的「優先度」一樣高，要怎麼辦？（這就是 `tie-breaking`）。如果輸入是空的、或只有一個元素，你的程式會炸掉嗎？
5. **對拍（最後的保險）：** 如果時間允許，特別是在考 `APCS` 時，寫一個「絕對正確但速度不快」的暴力解，然後用它來檢查你的貪心解在小規模的隨機資料下，答案是不是都一樣。這個技巧下面會再詳細講解。

---

## 對拍


什麼是對拍？
簡單來說，就是讓你的「貪心解」（我們叫他 `sol.cpp`）跟一個「暴力解」（我們叫他 `brute.cpp` 並且確保這個暴力解的答案絕對正確）來做比較

再白話點就是拿一個絕對正確但比較慢的程式來對答案

想法是：我們寫一個程式，自動產生一堆的隨機測試資料。對於每一筆資料，我們同時用 `sol.cpp` 和 `brute.cpp` 跑一次，然後比較它們的輸出。如果答案不一樣，那很顯然的我們抓到了一個你的貪心解會出錯的「反例 (counterexample)」。

這裡我們用「換硬幣最少枚數」來示範一次對拍。我們用「DP」當作保證正確的慢方法（標準答案），然後用隨機產生的測資，來挑戰我們的貪心寫法。（我知道還沒上過DP但是問題不大）

#include <bits/stdc++.h>
using namespace std;

// 相對慢但保證正確的解法：無限背包問題的 DP
// dp[x] 表示湊到 x 元所需要的最少硬幣數
int dp_min_coins(int X, const vector<int>& c) {
    const int INF = 1e9; // 用一個極大值表示湊不到
    vector<int> dp(X + 1, INF);
    dp[0] = 0; // 湊 0 元需要 0 個硬幣
    for (int x = 1; x <= X; ++x) {
        for (int v : c) {
            if (x - v >= 0) { // 如果可以從 x-v 轉移過來
                dp[x] = min(dp[x], dp[x - v] + 1);
            }
        }
    }
    return dp[X];
}

// 你想要測試的貪心寫法（從大到小拿）
int greedy_min_coins(int X, vector<int> c) {
    // 為了從大到小拿，先排序
    sort(c.begin(), c.end(), greater<int>());
    int cnt = 0;
    for (int v : c) {
        cnt += X / v; // 盡量拿當前面額的硬幣
        X %= v;       // 更新剩餘金額
    }
    // 如果最後 X 沒歸零，表示這個貪心湊不出來
    // 回傳一個極大值，方便和 DP 的 INF 比較
    return (X == 0) ? cnt : INT_MAX / 2;
}

int main() {
    // 這是 C++ 的隨機數產生器，比 rand() 更穩定好用
    // mt19937 rng(seed) 的 seed 可以隨便給一個數字，讓每次執行的隨機序列固定
    mt19937 rng(712271); 
    
    // 設定隨機數的範圍
    uniform_int_distribution<int> coinCnt(2, 5);     // 硬幣種類數：2~5 種
    uniform_int_distribution<int> coinVal(1, 30);    // 硬幣面額：1~30 元
    uniform_int_distribution<int> target(0, 200);    // 目標金額：0~200 元

    // 跑 5000 次測試
    for (int tc = 1; tc <= 5000; ++tc) {
        int m = coinCnt(rng); // 隨機決定這次要有幾種硬幣
        set<int> S; 
        S.insert(1); // 為了保證一定有解，我們強制加入 1 元硬幣
        while ((int)S.size() < m) {
            S.insert(coinVal(rng)); // 隨機加入其他面額 (set 會自動處理重複)
        }
        vector<int> coins(S.begin(), S.end()); // 從 set 轉成 vector

        int X = target(rng); // 隨機決定目標金額

        int ansDP = dp_min_coins(X, coins);
        int ansGreedy = greedy_min_coins(X, coins);

        if (ansDP != ansGreedy) {
            // 如果答案不一樣，立刻停下來並印出反例！
            cerr << "Found counterexample!\n";
            cerr << "Coins: ";
            for (int v : coins) cerr << v << " ";
            cerr << "\nX = " << X << "\n";
            cerr << "DP = " << ansDP << ", Greedy = " << ansGreedy << "\n";
            return 0; // 結束程式
        }
    }
    // 如果跑完都沒找到反例
    cerr << "No counterexample found in tests (doesn't prove correctness!).\n";
}

**小提醒：**
- **對拍沒抓到錯 ≠ 你的程式是正確的**。他只代表在你的隨機資料範圍內，暫時沒發現錯誤。可能反例太難抽，剛剛好躲過去。
- 真的要肯定這貪心是對的，心裡還是要有一個大致的證明邏輯。

- 寫對拍的一個前提是時間夠

---

## 貪心的常見錯誤


- **排序的依據搞錯了：** 就像活動選擇問題，直覺可能會想選「最短的活動」，但正解是「最早結束的」。排序的 `key` 選錯，整個貪心就死了。
- **忽略 `Tie-breaking` 的影響：** 當好幾個選項的優先度一樣時，你選擇的順序有時會影響到後續的決策，甚至影響最終答案的正確性，就像是有多個條件卻只判好最前面最大的條件。
- **目標函數看錯了：** 題目是要「最小化最大值」，還是「最小化總和」？兩者的解通常差別會不小。
- **忘了證明：** 尤其是在 `APCS` 這種後測環境，沒有線上評測可以直接幫你免費debug。結合「對拍」和「證明」才能真正確保這貪心是好的。

---

## 總結一下

- 貪心演算法的思路很直覺，但這種直覺需要被你自己的邏輯所驗證，至少要能說服自己。
- 主要的證明方法：**找反例**（通常是可以最快推出來）、**交換論證**（把別人的最佳解變成我的形狀）、**一路領先**（證明我每一步都不比別人差）。
- `APCS` 更好的應對方法：看到題目，可以大膽猜測貪心。但動手寫之前，先花幾分鐘思考一下證明，如果間允許寫一個對拍程式來當保險。提交前，你的心裡應該要有對這程式有一定的信心。

最後，就希望大家看得懂上面的一坨東西可以真的學好貪心


## 更多練習
講到這裡，你可能會覺得：「完蛋，我好像還是不太懂貪心要怎麼用」
沒是，問題不大。應該說，如果有人現在就能完全搞懂，那他可能才真的不太正常。

學貪心最好的方法就是透過寫題目來練手感。下面我們會帶大家看更多的經典題目。每一題，我們都會按照下面的流程來思考：
1. 這題到底能不能用貪心？
2. 如果可以，我的貪心策略是什麼？
3. 我要怎麼說服自己這個策略是對的？（證明）
4. 如果它是貪心，程式要怎麼寫？有哪些細節要注意？

---
這裡的例題，我們都會照著一個固定的流程來去寫，之後類似的題目也可以套用，不過這絕對不會是最好的所以僅供參考。

**解題前的小叮嚀：**
- **區間問題先看邊界：** 題目給的區間是 `半開半閉` `[s, e)` 還是 `全閉` `[s, e]`？這會直接影響你的判斷條件是用 `s >= lastEnd` 還是 `s > lastEnd`。差一個等號可能會差一題的分數。
- **看到「最大值的最小值」或「最小值的最大值」：** 這種題目有很高的機率可以用 `二分答案` + `貪心檢查` 的組合技來解決。
- **`APCS` 後測：** 因為沒有系統幫你試錯，所以「腦中有證明 + 手邊有對拍」才能確保你沒有被騙去假解(雖然做好也還是可能會被騙就是了)

---

## 1) CSES Movie Festival（最多不重疊區間｜活動選擇 的變形）


原題連結：[CSES Movie Festival](https://cses.fi/problemset/task/1629)

### 中文翻譯
### 題目描述
有一個電影節將播放 n 部電影。你知道每部電影的開始與結束時間。你想要觀看最多部完整的電影，且不能同時觀看兩部重疊的電影。

### 輸入格式
第一行為一個整數 n，表示電影部數。
接下來 n 行，每行包含兩個整數 a b，分別表示一部電影的開始與結束時間。

### 輸出格式
輸出你最多能完整觀看的電影部數。

### 輸入範例

3
3 5
4 9
5 8

### 輸出範例

2

### 思考引導：如何成為時間管理大師？

**情境：** 想像一下，你拿到了一張電影節的通票，上面列了 `n` 部電影的播放時間。每部電影都有一個開始時間 `s` 和結束時間 `e`。你的目標非常單純：**看盡可能多部電影**。你不是要看總時長最長的，而是要讓你看的「電影數量」最大化。

**釐清規則：**
- 你是個凡人，不能分身，所以同一時間只能在一個影廳看一部電影。
- 題目給的時間是 `[s, e)`，這是一個「左閉右開」區間。意思是，電影從 `s` 這個時間點開始播，但在 `e` 這個時間點**之前**就結束了。所以，在 `e` 這個時間點，你已經是自由的了，可以立刻去看下一部從 `e` 開始的電影。這點非常重要！

**可能出現的錯誤的直覺分析：**
- **「挑最短的電影看！」** 聽起來很直覺，短的電影比較不佔時間嘛。但想像一下，一部片長只有 `30` 分鐘的電影，卡在下午 `3:00` 到 `3:30`。你為了看它，可能會錯過一部從 `2:00` 播到 `3:00` 的電影，和另一部從 `3:30` 播到 `4:30` 的電影。你看了 `1` 部，卻放棄了 `2` 部。
- **「挑最早開始的電影看！」** 既然不能看最短的那我就看最早的嘛！但如果最早開始的是一部長達 `3` 小時的大長片，他可能會直接佔掉你一堆時間，錯過看好幾部短電影的機會。

**正確的思路引導：** 我們的目標是「最大化數量」，這代表說我們每做完一件事（看完一部電影），都希望「可以趕快騰出時間去看更多電影」。這個想法轉換成比較像程式的語言就是：**我們應該優先選擇那個能讓我們最早獲得自由的選項**。也就是，**結束時間最早的電影**。

---
### 能不能貪心?

先找出目前想到的規則跟直覺看

**規則：**
將所有電影依照結束時間 e 升冪排序。從頭掃描，如果當前電影的開始時間 s >= 上一部看完電影的結束時間 lastEnd，就選這部，並更新 lastEnd = e。

**直覺：**
一部電影越早結束，就越不會擋到後面的電影，留給未來的選擇空間就越大。

---
### 為什麼對?（交換論證）：
1. 先想像有一個時間管理大師羅志祥給了你一份「最優電影排程」，我們叫它 `O` (Optimal)。
2. 同時，我們也用我們的貪心策略排了一份清單，叫 `G` (Greedy)。
3. 比較 `O` 和 `G` 的**第一部電影**。`G` 選的一定是**所有電影中結束時間最早的**那部，我們叫它 `g1`。而 `O` 選的第一部電影，我們叫它 `o1`。
4. 因為 `g1` 是最早結束的，所以 `g1.e <= o1.e`。
5. 現在，如果我們把 `O` 排程裡的第一部電影 `o1`，強制換成 `g1`，會發生什麼事？因為 `g1` 結束得更早（或一樣早），所以這個新的排程（`g1` + `O` 的後續部分）絕對不會和後面的電影產生新的衝突。他留給後面的時間只會更多，不會更少。這個「被修改過」的 `O` 仍然是一個最優解。
6. 好，現在它們的第一部電影一樣了。我們繼續比較第二部、第三部... 每一步，我們都可以用同樣的「交換」手法，把 `O` 的選擇換成 `G` 的選擇，而不會讓結果變差。
7. 一路換到最後，你會發現，羅志祥的 `O` 排程，長得跟我們前面自己想的貪心的 `G` 一模一樣。這就證明了，我們的 `G` 和 `O` 一樣好，他就是一個最優解！

**核心不變量：** `在我們貪心選擇的過程中，已選清單中，最後一部電影的結束時間，永遠是當下可能的最早選擇。`

---
### 其他證明法（stays-ahead、歸納）
- `stays-ahead`（一路領先）：把 `貪心解 G` 跟 `最優解 O` 並排。對每個 `k`，`G` 的第 `k` 部會「不晚於」`O` 的第 `k` 部結束。每一步都不落後，最後不會選得比較少。
- 歸納：`k=1` 時，選 最早結束 一定不劣，假設前 `k-1` 步都不劣，第 `k` 步也選當前 `最早結束`，對後面傷害是最小的，所以不劣。

---
### 實作細節：

- **演算法步驟：**
1. 把所有電影（`s`, `e`）存成一個 `struct` 或 `pair` 的 `vector`。
2. 對這個 `vector` 進行排序，主要依據 `e` 升冪，次要依據 `s` 升冪 (`tie-breaking`)。
3. 初始化 `count = 0`，`lastEnd = -∞` (一個極小值)。
4. 遍歷排序後的 `vector`，對每部電影 `(s, e)`，如果 `s >= lastEnd`，就 `count++` 並且 `lastEnd = e`。
- **邊界條件：**
- 題目是 `半開區間` `[s, e)`，所以判斷條件是 `s >= lastEnd` (無縫接軌)。
- 如果是 `全閉區間` `[s, e]`，判斷條件就要改成 `s > lastEnd`。
- `s == e` 的零長度電影也是可以選的。
- **陷阱：**
- 排序鍵用成「電影長度 `e-s`」或「開始時間 `s`」。
- 把 `>=` 和 `>` 搞混。
- 雖然這題不嚴格要求，但 `tie-breaking` 是個好習慣，可以讓輸出在多種合法解中保持穩定。
- **複雜度：** `O(n log n)` + `O(n)` (掃描) = `O(n log n)`。

---
### 參考程式

// 建議將 {結束時間, 開始時間} 存成 pair，利用 pair 預設的排序規則
// pair 預設先比 first，first 相同再比 second
vector<pair<int, int>> movies;
// ... 讀取資料，記得存成 {e, s}
// for (int i = 0; i < n; ++i) { cin >> s >> e; movies.push_back({e, s}); }

sort(movies.begin(), movies.end());

int movies_watched = 0;
long long last_end_time = 0; // 用 0 當初始值即可，因為電影時間都是正數

for (const auto& movie : movies){
    int start_time = movie.second;
    int end_time = movie.first;
    if (start_time >= last_end_time){
        movies_watched++;
        last_end_time = end_time;
    }
}

---
### 對拍建議：
- `n <= 18`：枚舉所有子集（`2^n`），檢查子集內「兩兩不重疊」，取最大大小，和 `貪心` 答案比。
- 亂數：隨機 `s` 與長度，特別塞很多 `e==下一個 s`、`s==e` 當測試。

---

## 2) CSES Room Allocation（最少房間＋指定房號）


原題連結：[CSES Room Allocation](https://cses.fi/problemset/task/1164)

### 中文翻譯
### 題目描述
有一間大旅館，將有 n 位顧客入住。每位顧客需要一間單人房。你知道每位顧客的入住與退房日期。若一位顧客的退房日期早於另一位顧客的入住日期，則這兩位顧客可以住同一間房。

### 輸入格式
第一行為一個整數 n，表示顧客數。
接下來 n 行，每行兩個整數 a b，分別表示一位顧客的入住與退房日期。

### 輸出格式
第一行輸出所需最少房間數。
接下來 n 行，每行輸出一個整數，表示每位顧客被分配到的房號（房號從 1 開始）。

### 輸入範例

3
1 2
2 4
4 4

### 輸出範例

2
1
2
1

### 思考引導：如何當一個好的飯店櫃檯？

**思考：** 想像你是東京某某飯店的櫃檯人員，今天是日本最大漫展(應該?) `C106` 開始的日子，`n` 位宅宅會陸續抵達。你的電腦上有一份清單，記錄了每位客人的預計入住日 `l` 和退房日 `r`。客人們會嚴格按照「入住日」的順序來到你的櫃檯。

**你的基本任務：**
1. **節省成本：** 飯店老闆希望你盡可能地重複使用房間，目標是讓整個活動期間「總共使用到的房間數」最少。你不想沒事就開一間新房間來打掃。
2. **完成分配：** 你必須明確地告訴每一位客人，他被安排到幾號房。

**規則釐清：**
- 客人是按入住時間 `l` 排序好的。你必須依序處理他們。
- 房間重用的條件很嚴格：只有當前一位房客的退房時間 `r` **嚴格小於** (`<`) 下一位客人的入住時間 `l` 時，房間才能被騰出來給下一個人用。這意味著，如果有人住到 `12` 點退房，那麼 `12` 點整來入住的客人是不能使用這個房間的（可能需要時間打掃?）。

**錯誤的直覺分析：** 來一個客人，就從 `1` 號房開始找，找到第一間能住的就塞進去。這可能會出問題。假設 `1` 號房的客人明天早上 `9` 點就退房了，`2` 號房的客人要住三天。現在來了一個新客人，也要住三天。如果你隨便把他塞到 `1` 號房，那明天早上 `9:05` 又來一個客人時，他會發現 `1` 號房和 `2` 號房都被長住客佔了，被迫要開 `3` 號房。但如果你一開始把新來的長住客塞到 `2` 號房（假設也行），`1` 號房明天就能空出來給 `9:05` 的客人，省下一間房。

**正確的思路引導：** 關鍵在於「**有效管理可用的房間**」。當一個新客人 `(l, r)` 來到櫃檯時，最聰明的做法是：
1. **先更新狀態：** 看一下你的房間列表，把所有「已經可以退房了」（退房時間 `r_old < l`）的房間，全部從「使用中」移到「可可用」列表。
2. **再做決策：** 查看「可用」列表。
- 如果有空房，就從裡面挑一間給新客人（為了整齊，通常會挑房號最小的）。
- 如果完全沒有空房，那表示真的沒辦法(假設貪心是最佳)，必須開新房間。

---
### 能不能貪心?

**規則：**
`將所有客人按入住時間 l 升冪排序。依序處理每個客人：先把所有已退房 (r < l) 的房間丟回可用列表。如果可用列表有房間，就拿一個用，如果沒有，就開一間新的。`

**直覺：**
`只有在「真的完全沒有空房」的尖峰時刻，我們才需要開新房間。這個策略會讓我們使用的房間數，剛好等於「同時在住的最大人數」，這顯然是理論上的最少需求。`

---
### 為什麼對?（交換論證 或 必要下界證明）

這個問題的證明，用「必要下界」來想更直觀：
1. 想像在時間軸的某一個時間點 `t`，如果同時有 `k` 個人在旅館裡，那你至少需要 `k` 間房間，這是物理限制(畢竟他們剛離開漫展肯定帶了一堆奇怪的東西不想被看到)，不可能更少。
2. 整個時間軸上，「同時在住人數」的最大值，我們稱之為 `max_overlap`。那麼，任何合法的分配方案，都至少需要 `max_overlap` 個房間。
3. 我們的貪心策略是：只有在「沒有任何可用房間」時才開新的。這恰好發生在一個客人入住時，所有已開的房間都還有人住，也就是達到了某個「同時在住人數」的高峰。
4. 因此，我們策略所開的總房間數，正好就是 `max_overlap`。
5. 既然我們達到了理論上的最小值，那我們的策略自然就是最優的。

---
### 實作細節

- **資料結構：** 用 `priority_queue` 會很適合這題的需求。
- `busy_rooms` (最小堆)：存放 `{退房時間 r, 房號 id}`。堆頂永遠是「最早會空出來」的房間。
- `free_rooms` (最小堆)：存放可用的房號 `id`。用最小堆可以讓我們每次都優先分配房號較小的房間（題目要求）。
- **演算法步驟：**
1. 把客人資訊存成 `struct {l, r, original_id}`，並根據 `l` 排序。
2. 初始化 `room_count = 0`，兩個 `priority_queue`。
3. 遍歷排序後的客人：
a. `while (!busy_rooms.empty() && busy_rooms.top().first < current_guest.l)`：不斷從 `busy_rooms` 拿出已退房的房間，把房號丟進 `free_rooms`。
b. 檢查 `free_rooms`：如果不空，就從裡面拿一個房號 `id` 來用。如果空的，就新開一間 `id = ++room_count`。
c. 將 `{current_guest.r, id}` 放入 `busy_rooms`。
d. 記錄下這位客人的房號。
- **邊界：** 這題的規定是 `r < l` 才能重用，不是 `<=`。
- **陷阱：**
- 釋放房間的 `while` 迴圈寫成 `if`，只會釋放一個房間，是錯的。
- `<` 寫成 `<=`。
- 忘記把釋放的房號丟回 `free_rooms`。
- **複雜度：** `O(n log n)` (排序) + `O(n log n)` (每個客人進出堆一次) = `O(n log n)`。

---
### 參考程式

// 假設客人已按 l 排序，存在 vector<Guest> guests;
// busy_rooms: pair<int, int> -> {退房時間, 房號}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy_rooms;
// free_rooms: 存放可用的房號
priority_queue<int, vector<int>, greater<int>> free_rooms;
int room_count = 0;
vector<int> result(n); // 存放每位客人的房號

for (const auto& guest : guests){
    // 釋放房間
    while (!busy_rooms.empty() && busy_rooms.top().first < guest.l){
        free_rooms.push(busy_rooms.top().second);
        busy_rooms.pop();
    }
    
    int room_id;
    if (free_rooms.empty()){
        // 沒有空房，開新的
        room_id = ++room_count;
    } 
    else{
        // 有空房，拿最小號的來用
        room_id = free_rooms.top();
        free_rooms.pop();
    }
    
    // 分配房間給客人
    busy_rooms.push({guest.r, room_id});
    result[guest.original_id] = room_id;
}

---
### 對拍建議：小 `n` 只用 `暴力`
- 回溯法：`n <= 10`。對每個客人，遞迴地嘗試將他放入「目前已開的任一間房（需檢查不衝突）」或「新開一間房」。搜尋所有可能性，找到使用房間數最少的解。雖然這聽起來就很慢，但我們只需要拿來對貪心有沒有錯所以問題不大。

---

## 3) CSES Ferris Wheel（雙指針裝人）


原題連結：[CSES Ferris Wheel](https://cses.fi/problemset/task/1090)

### 中文翻譯
### 題目描述
有 n 個小孩想搭摩天輪。每個艙最多可以搭乘兩個小孩，且總重量不能超過 x。已知每個小孩的體重，請問最少需要多少個艙才能載完所有小孩？

### 輸入格式
第一行兩個整數 n 和 x，分別表示小孩數和每個艙的最大承重量。
第二行 n 個整數，分別表示每個小孩的體重。

### 輸出格式
輸出最少需要的艙數。

### 輸入範例

4 10
7 2 3 9

### 輸出範例

3

### 思考引導：如何最有效率地裝滿摩天輪？

**情境：** 你是遊樂園裡負責摩天輪的工作人員。有一長隊的小朋友在排隊。小朋友如果排隊太久就會開始亂叫，而你顯然不想聽到小孩亂叫，為了得到安靜的工作環境，你現在要做的就是用「最少的車廂數」把所有小朋友都送上去。

**規則釐清：**
- 每個車廂最多只能坐 `2` 個人。
- 每個車廂的總載重上限是 `x`。
- 每個小朋友都有自己的體重 `p_i`。

**錯誤的直覺分析：**
- **「從最輕的開始配對！」** 聽起來很安全，但可能會造成嚴重的浪費。想像一下，`x=100`，隊伍裡有 `[10, 20, 80, 90]`。如果你讓 `10` 和 `20` 坐一車，雖然很棒合法，但接下來 `80` 和 `90` 都太胖了，找不到第二個人可以跟他們坐，只能各自單獨坐一車。總共需要 `3` 個車廂。但如果你一開始讓 `10` 和 `90` 一組，`20` 和 `80` 一組，只需要 `2` 個車廂。

**正確的思路引導：** 在這個問題中，誰是「最麻煩」的？是**最重的人**。他的體重最佔額度，也最難找到可以跟他一起搭的人。所以，我們的策略應該是**優先解決最麻煩的問題**。
1. 先把所有小朋友按體重排好隊，從輕到重。
2. 每次都把注意力放在隊伍裡「最重」的那個小朋友身上。
3. 然後，為了盡可能地利用載重，我們試著從隊伍裡找一個「最不佔空間」的人來跟他搭配，也就是「最輕」的那個小朋友。
- 如果「最輕的」和「最重的」加起來沒超重 (`w_light + w_heavy <= x`)，太棒了！他們肯定是天作之合。讓他們一起上車。這樣我們一次就解決了最麻煩和最不麻煩的兩個人，是最高效的。
- 如果連「最輕的」都無法跟他湊一對，那更重的其他人肯定也不行。所以，這位最胖的小朋友只好委屈一下，享受他的單人包廂。

這個「一頭一尾」的配對思路，就是典型的「**雙指針**」技巧。

---
### 能不能貪心：一句話規則 + 一句話直覺

**規則：**
`將所有人按體重升冪排序。用兩個指針，i 指向最輕的，j 指向最重的。每輪處理 j：如果 w[i] + w[j] <= x，就把他們配對 (i++, j--)；否則，讓 j 單獨一車 (j--)。每輪車廂數都加一。`

**直覺：**
`優先處理最難配對的最重的人。如果連最輕的都救不了他，那就沒人救得了他了。`

---
### 為什麼對（交換論證）

讓我們來證明每一步的決策都是最優的：
1. **考慮最重的人 `j`：**
- **情況 A：如果最輕的人 `i` 可以和他配對 (`w[i] + w[j] <= x`)。**
我們的策略是讓他們配對。假設有另一個更優的解法，不讓他們配對。那會發生什麼？
- `j` 可能單獨一車：那我們把 `i` 隨便塞到別的車，結果不會比 `(i,j)` 一車更好。
- `j` 可能跟另一個 `k` (`i < k < j`) 配對：那 `i` 就得另外找車。這時，我們可以把 `(j, k)` 和 `i` 的配對，「交換」成 `(j, i)` 和 `k` 的配對。因為 `w[i] <= w[k]`，所以 `(j, i)` 肯定合法，而 `k` 自己單獨或找別人，情況不會更糟。所以把 `i` 和 `j` 配對，絕對不會更差。
- **情況 B：如果最輕的人 `i` 都不能和他配對 (`w[i] + w[j] > x`)。**
我們的策略是讓 `j` 單獨一車。這顯然是唯一選擇，因為沒有任何人比 `i` 更輕了。任何合法的方案都必須讓 `j` 單獨乘坐。

既然我們每一步都做了不會讓結果變差的選擇，那麼最終的結果就是最優的。

---
### 實作細節：

- **演算法步驟：**
1. 對體重陣列 `w` 進行升冪排序。
2. 設指針 `i = 0`, `j = n - 1`，答案 `ans = 0`。
3. `while (i <= j)`:
a. `ans++` (反正每輪都要用掉一個車廂)。
b. 如果 `i < j` 且 `w[i] + w[j] <= x`，表示可以配對，`i++`。
c. `j--` (最胖的人總是被處理掉)。
- **邊界條件：** 當 `i == j` 時，剩下最後一個人，他自己需要一個車廂。`while` 迴圈的條件 `i <= j` 能完美處理這種情況。
- **陷阱：**
- `i` 和 `j` 的更新順序搞錯。
- 忘記排序。
- `while` 迴圈條件寫成 `i < j`，會漏掉最後一個人。
- **複雜度：** `O(n log n)` (排序) + `O(n)` (雙指針掃描) = `O(n log n)`。

---
### 參考程式

sort(w.begin(), w.end());
int i = 0, j = w.size() - 1;
int cars = 0;
while (i <= j){
    cars++; // 先佔一個車廂
    // 讓最重的 j 上車，看看最輕的 i 能不能陪他
    if (i < j && w[i] + w[j] <= x){
        i++; // 如果可以，i 也上車
    }
    j--; // j 總是要上車的
}

---
### 對拍建議：小 `n` 只用 `暴力`
- 回溯法 (分箱問題)：`n <= 16`。對每個人，遞迴地嘗試將他放入「一個已存在的、還能再坐一人的車廂（需檢查總重）」或「一個新開的車廂」。窮舉所有可能性，找到最少車廂數。

---

## 4) CSES Array Division（答案二分 ＋ 貪心檢查）

原題連結：[CSES Array Division](https://cses.fi/problemset/task/1085)

### 中文翻譯
### 題目描述
給定一個長度為 n 的正整數陣列，請將它分割成 k 個連續子陣列，使得每個子陣列和的最大值最小。

### 輸入格式
第一行兩個整數 n 和 k。
第二行 n 個正整數，表示陣列內容。

### 輸出格式
輸出最小可能的最大子陣列和。

### 輸入範例

5 3
2 4 7 3 5

### 輸出範例

8

### 思考引導：從「求解」到「猜測」

**情境：** 想像你和一群朋友要去爬一座山，手上有張地圖，標示了連續 `n` 個路段的長度。你們計劃用 `k` 天走完。為了讓大家體力能平均分配，不要有一天累死、一天卻很輕鬆，你們希望規劃一個行程，使得「**路程最長的那一天，走的路程盡可能地短**」。這就是一個典型的「**最小化最大值**」問題。

**直接思考的困難：** 你要怎麼決定每天在哪裡結束（也就是陣列的切點）？切在這裡，好像會讓今天太長，切在那裡，又怕明天會太長。切點的可能組合數是天文數字，直接找最佳切點太難了！

**思路的轉變：** 與其直接問「最佳行程中，最長那天的路程是多少？」，不如我們換個角度來想想看。
- 我來猜一個數字，比如說 `X` 公里。然後我問你：「**我們能不能辦到，讓每天走的路都不超過 `X` 公里，並且在 `k` 天內走完？**」
- 這個「能不能辦到」的問題，就變得很簡單了！我們可以貪心的模擬一次行程：
- 第一天，盡量往前走，走到不能再走為止（再多走一個路段就會超過 `X`）。好，在這邊睡覺。
- 第二天，從營地出發，同樣盡量往前走...
- ...這樣一直走下去，最後看總共花了幾天。
- 這個檢查過程給了我們一個很強的結果：
- 如果這樣貪心走，花了超過 `k` 天，那說明我們猜的 `X` 太小了，每天走的路太少，必須把 `X` **放大**。
- 如果這樣貪心走，只花了 `k` 天或更少，那說明 `X` 是個可行的目標，甚至可能太大了，我們可以試試看更小的 `X`。
- 這個「`X` 越大，越容易在 `k` 天內完成」的**單調性**，就可以完美適配在「**二分答案**」。

你可能會說哭啊我又不會二分搜，沒事下節就是二分搜:D

---
### 能不能貪心?

**規則：**
`對「最大段和」這個答案進行二分搜。對於每個猜測的答案 x，用貪心策略檢查是否可行：從頭掃描陣列，能裝就裝，裝不下就切一段。最後看總段數是否 <= k。`

**直覺 (針對貪心檢查部分)：**
`在任何一個切點，如果你不盡量往後裝滿（在不超過 x 的前提下），而是提早切了一刀，只會讓後面的空間更緊張，導致未來可能需要切更多刀。所以，每一段都「裝到最滿」永遠是最優的策略。`

---
### 為什麼對（交換論證）

我們來證明「能裝就裝，超過了才切」的貪心檢查策略，會得到最少的段數。
1. 假設我們的貪心切法是 `G`，另一種任意合法的切法是 `A`。
2. 比較第一段。`G` 的第一段一定是「在和不超過 `x` 的情況下，盡可能長」。而 `A` 的第一段長度只可能小於或等於 `G` 的第一段。
3. 如果 `A` 的第一段比 `G` 的短，我們可以把 `A` 的第一個切點「向後推」，直到和 `G` 的一樣長。這樣做，`A` 的總段數不會增加，只可能減少或不變。
4. 現在 `G` 和 `A` 的第一段一樣了。我們接著看剩下的部分，這是一個完全相同的子問題。
5. 我們可以一路這樣「交換/調整」，把 `A` 的所有切點都調整到和 `G` 一樣，而總段數不會增加。
6. 結論：貪心切法 `G` 得到的段數，不多於任何其他切法。所以他是最少的。

---
### 實作細節：

- **二分答案的範圍：**
- 下界 `lo`：答案不可能比陣列中最大的單一元素還小。所以 `lo = max(a_i)`。
- 上界 `hi`：答案不可能比整個陣列的和還大。所以 `hi = sum(a_i)`。
- **注意：** 和可能會超過 `int`，記得用 `long long`。
- **`ok(x)` 檢查函式：**
1. `long long current_sum = 0; int segments = 1;` (一開始就算一段)。
2. 遍歷陣列中的每個數字 `v`：
a. 如果 `v > x`，說明這個數字自己就超標了，`x` 肯定不可行，直接 `return false`。
b. 如果 `current_sum + v > x`，說明裝不下了，需要切一刀。`segments++`，然後 `current_sum = v` (新的一段從 `v` 開始)。
c. 否則，`current_sum += v`。
3. 迴圈結束後，`return segments <= k`。
- **陷阱：**
- `segments` 初始值設成 `0` 是常見錯誤。
- 切分後，`current_sum` 要重設為 `v`，而不是 `0`。
- 二分搜的 `while(lo < hi)` 和 `lo = mid+1`, `hi = mid` 的更新邏輯要寫對，避免無窮迴圈。
- **複雜度：** `O(n log(sum_of_array))`。`log` 來自二分搜，`n` 來自每次的貪心檢查。

---
### 參考程式

// 檢查函式
auto is_possible = [&](long long max_sum){
    long long current_sum = 0;
    int segments = 1;
    for (long long val : a){
        if (val > max_sum) return false; // 單一元素就爆了
        if (current_sum + val > max_sum){
            segments++;
            current_sum = val;
        } 
        else{
            current_sum += val;
        }
    }
    return segments <= k;
};

// 二分搜主體
long long lo = *max_element(a.begin(), a.end());
long long hi = accumulate(a.begin(), a.end(), 0LL);
long long ans = hi;

while (lo <= hi){
    long long mid = lo + (hi - lo) / 2;
    if (is_possible(mid)){
        ans = mid;
        hi = mid - 1; // 試試看能不能更小
    } 
    else{
        lo = mid + 1; // 必須放寬上限
    }
}

---
### 對拍建議：小 `n` 只用 `暴力`
- DP 或 枚舉切點：`n <= 20`。可以用 `k-1` 個隔板插入 `n-1` 個空隙中，枚舉所有 `C(n-1, k-1)` 種切法。計算每種切法的「最大段和」，然後取所有切法中的最小值。

---

## 5) CSES Missing Coin Sum（最小不可湊金額）


原題連結：[CSES Missing Coin Sum](https://cses.fi/problemset/task/2183)

### 中文翻譯
### 題目描述
你有 n 枚硬幣，每枚硬幣有一個正整數面額。問你用這些硬幣可以湊不出的最小正整數是多少？

### 輸入格式
第一行一個整數 n。
第二行 n 個整數，分別表示每枚硬幣的面額。

### 輸出格式
輸出最小不能湊出的正整數。

### 輸入範例

5
2 9 1 2 7

### 輸出範例

6

### 思考引導：如何用手上的磚塊連續地鋪路？

**情境：** 想像你有一條從 `0` 開始的無限長的數線，代表所有金額。你還有一堆不同面額的硬幣，可以看作是不同長度的「磚塊」。你的任務是，從 `0` 點出發，用這些磚塊去鋪路，看能連續鋪多遠。第一個你鋪不到的、有空隙的正整數點，就是你要找的答案。

**思路：**
1. **初始狀態：** 你一塊磚塊都還沒用。你能到達的點只有 `0`。你能連續鋪滿的範圍是 `[0, 0]`。此時，第一個你到不了的正整數點是 `1`。我們把這個「目前連續鋪滿的終點」記為 `reachable_sum = 0`。
2. **拿起第一塊磚：** 為了最有效率地擴展我們的路，我們應該先從**最短的磚塊**（最小面額的硬幣）開始。假設最小的硬幣是 `c_1`。
3. **檢查與決策：**
- **情況一：如果 `c_1 > reachable_sum + 1`** (例如，`reachable_sum = 0`，但你最小的硬幣是 `2`)。這代表說，`1` 這個點你永遠也鋪不到，你手上的磚塊最小都是 `2`，你無法填補 `0` 和 `2` 之間的 `1` 這個空隙。遊戲結束，答案就是 `reachable_sum + 1`，也就是 `1`。
- **情況二：如果 `c_1 <= reachable_sum + 1`** (例如，`reachable_sum = 0`，你最小的硬幣是 `1`)。很開心的你原本能鋪滿 `[0, 0]`。現在多了長度為 `1` 的磚塊，你可以從原本能到的所有點（目前只有 `0`）出發，再往前鋪 `1`，於是你也能到 `0+1=1`。新的連續鋪滿範圍變成了 `[0, 1]`。你的 `reachable_sum` 更新為 `0 + 1 = 1`。
4. **繼續前進：** 現在 `reachable_sum = 1` (你能鋪滿 `[0, 1]`)。你拿起下一塊最小的磚塊 `c_2`。同樣檢查 `c_2` 是否大於 `reachable_sum + 1` (也就是 `2`)。
- 如果 `c_2 > 2`，那 `2` 這個點就鋪不到了，答案是 `2`。
- 如果 `c_2 <= 2` (比如 `c_2` 是 `1` 或 `2`)，你原本能鋪 `[0, 1]`，現在多了 `c_2`，你就能額外鋪出 `[0+c_2, 1+c_2]`。因為 `c_2` 不大，這兩個區間會連在一起，新的連續範圍擴展到 `[0, 1+c_2]`。`reachable_sum` 就更新為 `1 + c_2`。

這個推導過程可以得出：**必須先對硬幣排序**，然後一步步的擴展。

(相對前面這題更抽象一點，有問題的可以多消化或直接問)

---
### 能不能貪心?

**規則：**
`將所有硬幣升冪排序。維護一個目前能湊出的最小湊不出金額 res (初始為 1)。遍歷硬幣，如果當前硬幣 x > res，則答案就是 res；否則，將 res 更新為 res + x。`

**直覺：**
`從小面額的硬幣開始，一步步地填補數線上的空洞。一旦遇到一個硬幣，他的大小超過了我們目前第一個無法填補的洞，那這個洞就永遠補不起來了。`

---
### 為什麼對（歸納法）

這個證明用歸納法會很棒：
- **基礎情況：** 排序後，我們維護一個變數 `reachable_sum`，代表我們目前可以湊出 `[1, reachable_sum]` 之間的所有金額。一開始，一個硬幣都沒用，`reachable_sum = 0`。
- **歸納步驟：** 假設我們已經用了前 `i` 個硬幣，可以湊出 `[1, reachable_sum]`。現在我們考慮第 `i+1` 個硬幣，面額為 `x`。
- **情況 1：`x > reachable_sum + 1`**
我們能湊出的金額是 `[1, reachable_sum]`，以及用上 `x` 之後的 `x`, `x+1`, ...。但是在 `reachable_sum` 和 `x` 之間，出現了一個無法彌補的鴻溝。`reachable_sum + 1` 這個數字，因為 `x` 比他大，而之前能湊出的最大值又比它小，所以他絕對湊不出來。因此，答案就是 `reachable_sum + 1`。
- **情況 2：`x <= reachable_sum + 1`**
我們原本能湊 `[1, reachable_sum]`。現在多了硬幣 `x`，我們就能額外湊出 `[1+x, reachable_sum+x]`。因為 `x <= reachable_sum + 1`，這兩個區間 `[1, reachable_sum]` 和 `[1+x, reachable_sum+x]` 是相連或重疊的。他們合併之後，新的連續可湊範圍就變成了 `[1, reachable_sum + x]`。我們更新 `reachable_sum`，繼續考慮下一個硬幣。

排序保證了我們總是用最小的可用硬幣去嘗試填補最小的洞，這是最優的策略。

---
### 實作細節：

- **演算法步驟：**
1. 對硬幣陣列 `c` 進行升冪排序。
2. 初始化 `long long res = 1;`。
3. 遍歷排序後的 `c`，對每個硬幣 `x`：
a. 如果 `x > res`，直接 `break`。
b. 否則，`res += x`。
4. 最終答案就是 `res`。
- **邊界：** 如果排序後第一個硬幣就不是 `1`，答案直接是 `1`。我們的程式可以自然處理這種情況。
- **陷阱：**
- 忘記排序，這是此題貪心的基礎。
- `res` 的累加和可能很大，必須用 `long long`。
- **複雜度：** `O(n log n)` (排序) + `O(n)` (掃描) = `O(n log n)`。

---
### 參考程式

sort(coins.begin(), coins.end());

long long smallest_unreachable = 1;
for (long long coin_value : coins){
    if (coin_value > smallest_unreachable){
        // 出現了無法彌補的缺口
        break;
    }
    // 這個硬幣可以幫我們把可達範圍擴大
    smallest_unreachable += coin_value;
}

cout << smallest_unreachable << endl;

---
### 對拍建議：小 `n` 只用 `暴力`
- `n <= 20`：用位元枚舉 `2^n` 種所有子集，計算出所有可能的和，存到一個 `set` 或 `bool` 陣列中。然後從 `1` 開始，一個一個檢查哪個數字最先不在集合裡。

---

## 6) LeetCode 55. Jump Game（能不能到最後一格）


原題連結：[Jump Game](https://leetcode.com/problems/jump-game/)

### 中文翻譯
### 題目描述
給定一個非負整數陣列 `nums`，你一開始位於陣列的第一個位置。每個元素代表你在該位置最多可以向前跳幾步。判斷你是否能跳到最後一個位置。

### 輸入格式
一個整數陣列 `nums`。

### 輸出格式
布林值（true/false），表示是否能跳到最後一格。

### 輸入範例

[2,3,1,1,4]

### 輸出範例

true

### 輸入範例2

[3,2,1,0,4]

### 輸出範例2

false

### 思考引導：青蛙過河，只問能否到達對岸

**情境：** 想像有一隻青蛙，要從河的一邊跳到另一邊。河上有一排 `n` 片荷葉，編號從 `0` 到 `n-1`。青蛙一開始在 `0` 號荷葉上。每一片荷葉 `i` 上都寫著一個數字 `nums[i]`，這個數字代表青蛙在這片荷葉上，最多可以往前跳 `nums[i]` 片荷葉遠。

**核心問題：** 這隻青蛙「**有沒有可能**」成功跳到最後一片荷葉 (`n-1`)？注意，題目只問「**可能性**」，不問「怎麼跳」或「最少跳幾次」。

**錯誤的思路：** 「我要把所有可能的跳法都試一遍！」但這就像一個巨大的迷宮，從 `0` 出發，每個點都有好多條岔路，用 `DFS` 或 `BFS` 去窮舉所有路徑，在陣列很大時會跑到下輩子，吃到 `TLE` (雖然我們也還沒教圖論就是了:0)。

**正確的思路引導：** 我們可以換一個更好的角度。與其關心多到不可思議的路徑可能，不如只關心一個簡單的問題：「**以我目前的能力，最遠可以踏上哪一片荷葉？**」
1. 我們用一個變數 `max_reach` 來記錄這個「最遠可以跳到的荷葉」。一開始，我們在 `0` 號荷葉，所以 `max_reach` 初始就是 `nums[0]`。
2. 然後，我們像青蛙一樣，一片一片荷葉往前走（`for i = 0 to n-1`）。
3. 在踏上每一片新的荷葉 `i` 之前，都必須先來一次靈魂拷問：「**我現在要去的 `i` 號荷葉，是我之前能跳到的地方嗎？**」如果 `i` 比我已知的 `max_reach` 還要遠，那就表示這片荷葉太遠，根本到不了。既然 `i` 都到不了，後面的 `i+1`, `i+2`... 更不可能到。直接結束，`return false`。
4. 如果 `i` 是可達的 (`i <= max_reach`)，那很開心了。這片荷葉 `i` 就成了我們新的「起點」。我們可以從這裡奮力一跳，最遠能到 `i + nums[i]`。我們立刻用這個新的最遠距離，來更新我們的世界觀：`max_reach = max(max_reach, i + nums[i])`。
5. 只要我們一路走，都沒有遇到「到不了」的荷葉，就表示通往終點的路是暢通的。

---
### 能不能貪心?

**規則：**
`維護一個最遠可達位置 max_reach。從頭掃描陣列，如果當前位置 i > max_reach，則失敗，否則，用 i + nums[i] 更新 max_reach。`

**直覺：**
`我不在乎過程，只在乎我能觸及的邊界在哪。每走一步，我都利用當前的起點，盡力把這個邊界推得更遠。`

---
### 為什麼對（歸納法）

這個貪心策略的正確性很直覺
- `max_reach` 的定義是「從 `index 0` 到 `i-1` 這些位置出發所能到達的最遠 `index`」。
- 當我們考慮 `index i` 時：
- 如果 `i > max_reach`，根據定義，`i` 根本無法從 `0` 到 `i-1` 的任何地方跳過來，所以 `i` 是不可達的。
- 如果 `i <= max_reach`，說明 `i` 是可達的。那麼，我們就有機會利用 `i` 這個新的起點，將我們的可達範圍擴展到 `i + nums[i]`。
- 這個過程保證了 `max_reach` 總是正確的反映了當前探索過的部分所能到達的最遠點。只要在遍歷過程中 `max_reach` 始終能覆蓋到當前的 `i`，就說明路是通的。

---
### 實作細節：

- **步驟：**
1. `int max_reach = 0;`
2. `for (int i = 0; i < n; ++i)`:
a. `if (i > max_reach) return false;`
b. `max_reach = max(max_reach, i + nums[i]);`
c. (優化) `if (max_reach >= n - 1) return true;`
3. `return true;` (或根據迴圈結束條件判斷)
- **邊界：**
- `n = 1`：直接 `true`。
- `nums[0] = 0` 且 `n > 1`：`max_reach` 會一直是 `0`，當 `i=1` 時就會 `return false`。
- **陷阱：**
- 想得太複雜，去用 `BFS/DFS`，導致超時。
- `max_reach` 更新的時機或邏輯寫錯。
- **複雜度：** `O(n)`，只需要一次線性掃描。

---
### 參考程式

int max_reach = 0;
for (int i = 0; i < nums.size(); ++i){
    // 如果當前位置已經超過了我們能到達的最遠距離，那就不可能繼續了
    if (i > max_reach){
        return false;
    }
    // 更新最遠可達距離
    max_reach = max(max_reach, i + nums[i]);
}
// 如果迴圈能跑完，表示最後一格至少是可以被觸及的
return true;

---
### 對拍建議：小 `n` 只用 `暴力`
- `n <= 25`：用 `DFS` 或 `BFS`。從 `index 0` 開始，把所有能跳到的位置加入佇列，並用一個 `visited` 陣列避免重複訪問。看最終 `visited[n-1]` 是否為 `true`。
---

## 7) LeetCode 455. Assign Cookies（最大化滿足人數）


原題連結：[Assign Cookies](https://leetcode.com/problems/assign-cookies/)

### 中文翻譯
### 題目描述
你是一位很棒的父母，有多個孩子和多塊餅乾。每個孩子有一個胃口值，每塊餅乾有一個大小。每個孩子最多只能得到一塊餅乾，且只有餅乾大小大於等於孩子胃口值時，該孩子才會滿足。問你最多能滿足多少孩子。

### 輸入格式
兩個整數陣列 g 和 s，分別表示每個孩子的胃口值和每塊餅乾的大小。

### 輸出格式
一個整數，表示最多可以滿足的孩子數。

### 輸入範例

g = [1,2,3], s = [1,1]

### 輸出範例

1

### 輸入範例2

g = [1,2], s = [1,2,3]

### 輸出範例2

2

### 思考引導：如何當一個合格的商人？

**情境：** 你開了一家餅乾店，今天店裡來了一群小朋友，也剛好出爐了一批餅乾。
- **需求方：** 每個小朋友都有一個「最低要求」，可以看作是他的「胃口」`g_i`。餅乾的大小必須**大於或等於**他的胃口，他才會心滿意足的收下。(好貪心的小朋友)
- **供給方：** 每塊餅乾都有一個具體的大小 `s_j`。
- **目標：** 你想讓盡可能多的小朋友開心。也就是「**最大化被滿足的小朋友數量**」。

**思路：**
- 你面前站著一群高矮胖瘦不同的小朋友（胃口不同），手裡拿著一盤大小不一的餅乾。你該怎麼開始分配？
- **考慮最挑剔的客人？** 也就是胃口最大的小孩。你可能需要用你手上最大塊的餅乾才能滿足他。這似乎是個方向。
- **考慮最不挑剔的客人？** 也就是胃口最小的小孩。他很容易被滿足。我們應該用哪塊餅乾給他呢？如果用一塊超大的餅乾，雖然他很開心，但這塊大餅乾本來可以去滿足一個胃口很大的小孩。這樣做似乎很浪費。但如果我們用一塊「剛剛好能滿足他」或「比他胃口大一點點」的餅乾給他，是不是更划算？這樣我們就把更大的餅乾，留給了那些更貪心的大胃王。
- 這個思路引導我們：**應該優先處理最容易滿足的需求，並用最低的成本來滿足它**。也就是，讓**胃口最小**的小孩，去嘗試匹配**尺寸最小**的餅乾。

這就有點像是前面的摩天輪問題了(所以為甚麼小朋友都要用雙指針解?)

---
### 能不能貪心?

**規則：**
`將小孩的胃口 g 和餅乾的大小 s 都進行升冪排序。用兩個指針，i 指向小孩，j 指向餅乾。如果當前餅乾 s[j] 能滿足當前小孩 g[i]，則配對成功 (ans++, i++, j++)，否則，說明這塊餅乾太小了，連最小胃口的小孩都滿足不了，只能換一塊更大的餅乾 (j++)。`

**直覺：**
`用最小的代價去滿足最容易滿足的需求，把大資源留給更困難的需求。`

---
### 為什麼對（交換論證）

1. 將 `g` 和 `s` 排序。考慮胃口最小的小孩 `g[0]`。
2. 為了滿足他，我們需要找一塊 `s[j] >= g[0]` 的餅乾。我們的貪心策略是，找滿足條件的 `s` 中，最小的那一塊，也就是 `s[k]` (`k` 是最小的 `j` 使得 `s[j] >= g[0]`)。
3. 假設有一個最優解，他沒有用 `s[k]` 來滿足 `g[0]`，而是用了另一塊更大的餅乾 `s[l]` (`l > k`)。同時，`s[k]` 可能被用來滿足了另一個胃口更大的小孩 `g[m]` (`m > 0`)，或者沒被使用。
- 如果 `s[k]` 滿足了 `g[m]`，那麼 `s[k] >= g[m]`。因為 `g[m] >= g[0]`，所以我們有 `s[l] > s[k] >= g[m] >= g[0]`。
我們可以進行「交換」：讓 `s[k]` 去滿足 `g[0]`，讓 `s[l]` 去滿足 `g[m]`。
- `s[k] >= g[0]` 嗎？是的，因為 `s[k]` 連 `g[m]` 都能滿足。
- `s[l] >= g[m]` 嗎？是的，因為 `s[l]` 是更大的餅乾。
- 交換後，滿足的人數不變。我們成功的把最優解「修正」成了我們的貪心選擇，而結果沒有變差。
4. 通過一路交換，任何最優解都可以被轉換成我們的貪心解。因此，貪心解是最優的。

---
### 實作細節：

- **演算法步驟：**
1. 對 `g` 和 `s` 升冪排序。
2. `int i = 0, j = 0, ans = 0;`
3. `while (i < g.size() && j < s.size())`:
a. `if (s[j] >= g[i])`: 滿足了！`ans++`, `i++`, `j++`。
b. `else`: 這塊餅乾太小，換下一塊。`j++`。
- **陷阱：**
- 忘記排序。
- 用大餅乾去滿足小胃口，雖然也是一種貪心，但那是錯誤的想法。
- **複雜度：** `O(g log g + s log s)` (排序) + `O(g + s)` (掃描)。

---
### 參考程式

sort(g.begin(), g.end()); // 胃口排序
sort(s.begin(), s.end()); // 餅乾大小排序

int child_ptr = 0;
int cookie_ptr = 0;
int satisfied_children = 0;

while (child_ptr < g.size() && cookie_ptr < s.size()){
    // 如果當前最小的餅乾能滿足當前胃口最小的小孩
    if (s[cookie_ptr] >= g[child_ptr]){
        satisfied_children++;
        child_ptr++; // 換下一個小孩
        cookie_ptr++; // 用掉這塊餅乾
    } 
    else{
        // 這塊餅乾太小了，連胃口最小的都滿足不了，只能換塊大的試試看
        cookie_ptr++;
    }
}

---
### 對拍建議：小 `n` 只用 `暴力`
- `n, m <= 12`：用回溯法或 DP。例如，`dp[i][j]` 表示用前 `j` 塊餅乾最多能滿足前 `i` 個小孩的人數。

---

## 複習一下

- **`規則` 怎麼挑？** 想像你在省資源：越早釋放（活動結束早）、先搞定最麻煩的（最重先配）、能裝就裝（切段）。
- **`證明` 怎麼弄？** 三句話：
1. 我每一步選 XXX；
2. 把別的解換成 XXX 不會變糟（更早結束／更省空間／更有彈性）；
3. 一路換到和我一樣，所以我不比最優差。
- **`對拍` 怎麼做？** 小範圍，只用暴力：子集枚舉、切點枚舉、回溯配對、BFS/DFS。亂數多塞邊界（等號、零長度、剛好=上限、一個超大其餘超小）。第一個不一致就把測資縮小、抓 `bug`。

---

廢話:這次嘗試把重點包起來，希望好讀一點
然後原本編了八題，但考慮那有點小難加上似乎太多了所以被我砍了:0
然後這次搞了三萬字，很有生活