# 貪婪演算法(greedy algorithm)
貪婪演算法，又稱貪心演算法

貪婪演算法在每一步決策中選擇當前看似最好的選項，目的在尋找**局部最優解**而非一定為**全局最優解**

給個例子，你有若干個1元、5元、10元硬幣，如果需要湊出16元，最少需要幾個硬幣？

`coins = 0, cnt = 0`
優先選擇最大面額(10元)
`coins = 1, cnt = 10`
10元會超出所求，選擇第二高面額(5元)
`coins = 2, cnt = 15`
最後選擇1元
`coins = 3, cnt = 16`

故答為 `3`

## 例題
:::success
### [ntucpc- [Tutorial] 好吃的蛋糕](https://oj.ntucpc.org/problems/97)
:::
:::spoiler 解題思路
將好吃度排序，並從最大開始加總$K$個，最後輸出
:::
:::spoiler WA
注意數字的大小
:::
:::spoiler AC Code
時間複雜度$O(N\ log\ N)$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long

vector<ll> v;

int main(){
    ll n, k; cin >> n >> k;
    for(ll i = 0, tmp; i < n; i++){
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end()); //O(log N)

    ll ans = 0;
    for(int i = n-1; i >= n-k; i--){
        ans += v[i];
    }
    cout << ans;
    return 0;
}

:::
:::success
### [ntucpc- [Tutorial] 趕不完的作業](https://oj.ntucpc.org/problems/98)
:::
:::spoiler 解題思路
一樣排序，但要考慮作業的截止時間，並且要在寫完一份作業後改變當前時間
:::
:::spoiler AC Code
時間複雜度$O(N\ log\ N)$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long

vector<ll> v;

int main(){
    ll n, k; cin >> n;
    for(ll i = 0, tmp; i < n; i++){
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end()); //O(log N)

    ll ans = 0, t = 0;
    for(int i = 0; i < n; i++){
        if(v[i] >= t + 1){ //截止前1小時要完成
            t++;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

:::
:::warning
### [ntucpc- [Tutorial] 趕不完的作業2](https://oj.ntucpc.org/problems/99)
:::
:::spoiler 解題思路
記得「模擬」寫作業過程經過的時間，並且考慮做一份作業後接下來還可以做哪些
:::
:::spoiler AC Code
時間複雜度$O(N\ log\ N)$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, l; cin >> n >> l;
    vector<int> v(n);
    for(auto &i : v) cin >> i;
    sort(v.begin(), v.end());
    int t = 0, ans = 0;
    for(auto i : v){
        if(i < l || i-t < l) continue;
        t += l;
        ans++;
    }
    cout << ans << "\n";
    return 0;
}

:::
:::warning
### [ntucpc- 1072 . A.誰先晚餐](https://tioj.ck.tp.edu.tw/problems/1072)
:::
:::spoiler 解題思路
每個人吃完一份餐的速度必為$t+C_i+E_i$分鐘，因此邊計算$max$邊模擬做菜過程即可
:::
:::spoiler tips
「多組測試資料」
:::
:::spoiler AC Code
時間複雜度$O(N\ log\ N)$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    while(true){
        cin >> n;
        if(n == 0) break;
        vector<pair<int, int>> v; //{E, C}
        for(int i = 0; i < n; i++){
            int c, e; cin >> c >> e;
            v.emplace_back(e, c);
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        int t = 0, mx = -1e9;
        for(auto i : v){
            auto [e, c] = i;
            mx = max(mx, t + c + e);
            t += c;
        }
        cout << mx << "\n";
    }
    return 0;
}

:::
:::warning
### [ntucpc- 713 . 餐點順序](https://oj.ntucpc.org/problems/713)
:::
:::spoiler 解題思路
實際推演後可以發現到，||先做花費時間少的為局部最優解||
:::
:::spoiler AC Code
時間複雜度$O(N\ log\ N)$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    long long n; cin >> n;
    vector<long long> v(n);
    for(auto &i : v) cin >> i;
    sort(v.begin(), v.end());
    long long p = n; //still waiting
    long long ans = 0;
    for(auto i : v){
        ans += (long long)(i * p);
        p--;
    }
    cout << ans << "\n";
    return 0;
}

:::
:::info
### <font color = "#9894F9"> 武陵高中114學科能競校內初選- pF Restaurants Around WLSH </font>
(沒有連結只是好看)
此題無judge，公開測資對則正確
###### ~~小小碎碎念：這題會留著是因為我打完這些說明後發現沒有judge，但我打很久所以留下來了~~
:::
#### **Description**：
:::spoiler Description
零換粥是一名五零高中的學生，有一天晚上他留下來和同學吃飯，正當他們踏出校門時，他們遇到了世紀三大謎題之一———「晚餐要吃什麼」。身為五零老屁股，零換粥拿出了珍藏的美食餐廳清單，上面依序寫了他對每間餐廳的喜好度排名。為了不要白跑一趟，他們打算先查好每間餐廳有沒有開，再去喜好度排名最前面（數字最小）的餐廳。已知每間餐廳分別被編號為$1 ∼ N$ ，現在給你這份美食餐廳清單，以及每間餐廳的營業狀況，請你判斷他們應該要去哪間餐廳吃飯。
:::

#### **Input**
:::spoiler Input
輸入的第一行是一個正整數 $N$，代表餐廳的數量。第二行有$N$ 個正整數，其中第 $i$ 個整數 $x_i$ 代表第 $i$ 間餐廳的喜好度排名。第三行有 $N$ 個正整數，皆為 $1$ 或 $0$ ，其中第 $i$ 個整數 $y_i$ 代表第 $i$ 間餐廳的營業狀況（$1$ 代表有營業，$0$ 代表沒有營業）。
* $1 ≤ N ≤ 10^6$
* 對於所有$1 ≤ i ≤ N，1 ≤ x_i ≤ N$ ，保證$x_i$ 互不相同。
* 對於所有$1 ≤ i ≤ N，yi ∈ \{0, 1\}$ ，保證至少有一個$y_i$ 為 $1$。
:::
#### **Output**
:::spoiler Output
輸出一個整數，代表他們最後選擇的餐廳的編號（亦即所有有營業的餐廳中，排名最前面的餐廳的編號）。
:::

#### **Samples**
:::spoiler Samples
| Sample No. | Input | Output |
|:---------- |:---------------------------------------------------------------------------- |:------ |
| 1 | 3 <br> 2 3 1 <br> 0 1 0 | 2 |
| 2 | 10 <br> 1 2 3 4 5 6 7 8 9 10 <br> 1 1 1 1 1 1 1 1 1 1 | 1 |
| 3 | 15 <br>9 15 4 10 13 6 2 12 5 8 7 1 14 3 11 <br>0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 | 15 |
:::
:::spoiler AC Code
||(by GDD) orzz||

#include <iostream> 
using namespace std; 
  
#define ll long long; 
  
ll N; 
ll A[1000010]; 
  
int main(){ 
    cin >> N; 
    for(int i = 1; i <= N; i++) cin >> A[i]; 
  
    ll idx = -1; 
    for(ll i = 1, v; i <= N; i++){ 
        cin >> v; 
        
        if(v){ 
            if(idx == -1) idx = i; 
            else{ 
                if(A[i] < A[idx]) idx = i; 
            } 
        } 
    } 
  
    cout << idx << '\n'; 
  
    return 0; 
}

:::
:::danger
### [CSES- Tasks and Deadlines](https://cses.fi/problemset/task/1630/)
:::
#### 題目敘述翻譯
你有 $n$ 個任務要處理，且每個任務都須完成不能不做。
每個任務都有持續時間 $a$ 和截止日期 $d$。
每完成一個任務，會獲得 $(\ d-完成時間f\ )$ 的收益，此數值有可能為負
如果你採取最優行動，你的最大收益總和是多少？
:::spoiler 解題思路
對於局部最優解而言，選擇先做持續時間短的比做截止日期近的較優，類似「誰先晚餐」的解題思路，持續時間會影響到後續的幅度比日期多。

因此此題應先將資料按照持續時間由小排到大，再根據題目做運算

###### ~~注意: 資料範圍~~~~
:::
:::spoiler AC code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n; cin >> n;
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        int a, d; cin >> a >> d;
        v.emplace_back(a, d);
    }
    sort(v.begin(), v.end());
    long long t = 0, ans = 0; //10^6 * (2 * 10^5)

    for(auto i : v){
        auto [a, d] = i;
        t += a;
        ans += (d - t);
    }

    cout << ans;
    return 0;
}

:::
>[!NOTE]...待新增...