【C++】競程筆記（貪心法則、貪婪演算法）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
註：本篇筆記是作者本人腦子最燒的一篇。
---
貪婪演算法（greedy algorithm）
---
又稱貪心法則，最常見的例子就是排程問題。
貪婪演算法在每一步決策中選擇當前看似最好的選項，其核心在於追求「局部最優解」，而非保證「全局最優解」。
縮短一下句子，貪婪演算法就是每一步選目前最好的就對了。
若一道題目要得到全局最優解，則應該要考慮使用動態規劃（Dynamic Programming）演算法。
對，貪心法就這樣，剩下就是靠做題目去抓感覺，但是貪心法就跟動態規劃一樣鬼，題目可以給你出得很簡單很甜，有時候可以給你難到嚇嚇叫，做個題目想個一天還不一定想得出來（被這些題目蹂躪過的作者表示）。
### [Tutorial] 好吃的蛋糕
---
Source：https://oj.ntucpc.org/problems/97
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N, K;
cin >> N >> K;
vector <long long> y(N);
for (int i = 0; i < N; i++){
cin >> y[i];
}
sort(y.begin(), y.end());
long long sum = 0;
for (int i = N - K; i < N; i++){
sum += y[i];
}
cout << sum;
return 0;
}
```
時間複雜度： $O(NlogN)$
解題思路為將資料排序，然後找最小的 N - K 之後元素的總和即可。
能降至 $O(N)$ 的方法：
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<long long> y(N);
for (int i = 0; i < N; i++) {
cin >> y[i];
}
nth_element(y.begin(), y.begin() + N - K, y.end());
long long sum = 0;
for (int i = N - K; i < N; i++) {
sum += y[i];
}
cout << sum;
return 0;
}
```
### [Tutorial] 趕不完的作業
---
Source：https://oj.ntucpc.org/problems/98
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<long long> d(N);
for (int i = 0; i < N; i++) {
cin >> d[i];
}
sort(d.begin(), d.end());
long long t = 0;
int counts = 0;
for (int i = 0; i < N; i++) {
if (d[i] >= t + 1) {
counts++;
t++;
}
}
cout << counts;
return 0;
}
```
解題思路與上題差不多，需要將資料排序，並且透過遍歷跟條件去做判斷。
counts 為作業數，t 為耗時，題目敘述也說了，每做一份作業就需要花 1 小時來做，且有機會將只有一個小時後截止的作業完成（也就是能在 deadline 做完），所以這邊判斷 `d[i] >= t + 1`。
### 誰先晚餐
---
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N;
while (cin >> N) {
if (N == 0) break;
vector<pair<int, int>> jobs(N);
for (int i = 0; i < N; i++) {
cin >> jobs[i].first >> jobs[i].second;
}
sort(jobs.begin(), jobs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
});
int cumulative_time = 0;
int max_finish = 0;
for (const auto& job : jobs) {
cumulative_time += job.first;
int finish_time = cumulative_time + job.second;
if (finish_time > max_finish) {
max_finish = finish_time;
}
}
cout << max_finish << "\n";
}
return 0;
}
```
第一次交的時候 WA，發現我忘記這是 EOF，忘記加 "\n" XD。
這邊用到 STL 的 pair，因為有 $C_{i}, E_{i}$ ，兩者是有關聯的，所以用上了所謂的關聯式容器 pair。
然後 sort() 部分用到了 lambda 函數，原因是我覺得這樣比較省麻煩，寫成一般函數就長這樣（比較直觀一點）：
```cpp=
bool compare_func(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
```
然後有個細節就是這邊要以 $E_{i}$ 去排序，因為在直觀上，如果吃飯時間長的人排在後面，那等於說我們飯都吃完了，就他沒吃完，等於說還要等他，再加上大的 $E_{i}$ ，可能導致總時間增加。
那至於是要讓 $E_{i}$ 升序還是降序呢？答案當然是降序，以最大吃飯時間的人為優先，就以這題範例測資來講：
```
1 1
2 2
3 3
```
改成降序之後就是：
```
3 3
2 2
1 1
```
因為題目輸出要求算的是所有時間的加總（到最後一人吃完為止），所以可列下表：
| 第 i 人 | 煮菜時間 | 吃飯時間 | 加總 |
| -------- | -------- | -------- | -------- |
| 1 | 3 | 3 | 6 |
| 2 | 5 | 2 | 7 |
| 3 | 6 | 1 | 7 |
至於這個 5、6 就是加前面的時間，5 = 3 + 2、6 = 3 + 2 + 1。
然後要將加總的資料 max() 取最大值，因為每人吃飯快慢不同，如果有人先吃完了，但其他人都還在吃就等於說還要等他吃完才可以走。
在這支程式裡面，cumulative_time 變數就是累計時間，max_finish 為最大完成時間。
30 行：做菜時間直接存入變數 cumulative_time 裡面。
31 行：從做完一道菜到吃完的時間和。
### 物品堆疊
---
Source：https://zerojudge.tw/ShowProblem?problemid=c471
有些貪心法的題目並非像前述那樣直觀，像這題的貪心就比較難一點。
題目主要敘述將 $N$ 個物品垂直堆疊在貨架上，每個物品有重量 $w(i)$ 和取用次數 $f(i)$ ，目標是找到一個排列順序，使得取用所有物品時消耗的總能量最小。每次取用某個物品時，需要先將其上方的所有物品升高，消耗的能量等於這些物品的總重量乘以該物品的取用次數（ $w(i) \times f(i)$ ）。
再來題目有列出幾個排列情形，然後我們要在這裡面找到最好的排列情形，根據範例，可以發現：物品的排列順序跟 $\frac{f(i)}{w(i)}$ （取用次數除以重量）的比值相關。
若將物品依照 $\frac{f(i)}{w(i)}$ 由大到小排序（比值大的物品放在上面，比值小的放在下面），可以最小化總能量的消耗。
可以這樣想：比值大的就表示物品輕，但取用頻率高，放在上面可以減少被其他物品抬升的次數，從而降低總能量。反之，比值小的物品（重量大或取用次數少）放在下面，雖然取用時要抬升上面的物品，但因為 $f(i)$ 小，所以影響不大。
那再來是考慮時間複雜度的問題了，最常見做法就是資料排序 -> $O(NlogN)$ ， $O(N)$ 的做法想不出來所以算了，因為題目測資沒那麼嚴格，以 $O(NlogN)$ 來說就夠用。
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct Item {
int w, f;
};
bool compare(const Item& a, const Item& b) {
return (long long)a.f * b.w > (long long)b.f * a.w;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<Item> items(N);
for (int i = 0; i < N; i++) {
cin >> items[i].w;
}
for (int i = 0; i < N; i++) {
cin >> items[i].f;
}
sort(items.begin(), items.end(), compare);
vector<long long> suf_f(N + 1, 0);
for (int i = N - 1; i >= 0; i--) {
suf_f[i] = suf_f[i+1] + items[i].f;
}
long long E = 0;
for (int k = 0; k < N - 1; k++) {
E += (long long)items[k].w * suf_f[k + 1];
}
cout << E << "\n";
return 0;
}
```
自定義排序部分有個小細節，前面不是說比值大排前面，小的排後面嗎？但因為如果程式直接這樣除，會有浮點數誤差的問題存在，所以我們把它交叉相乘，就變成 $f(a) \times w(b) > f(b) \times w(a)$ 。
而這邊的程式碼也使用到了後綴和，那為啥使用後綴和？因為前綴和是「從開頭到某點」的總和，而後綴和為「從某點到結尾」的總和，再加上使用前綴和需要額外計算和邊界處理，會增加時間複雜度。而 `suf_f[k + 1]` 表示從第 $k + 1$ 個物品到最後一個的 $f$ 總和。
如果 N 超過兩個以上，我們就需要將這個 E 累加。因為最上面的物品不需要耗能，所以不會被計算到 E 裡面，可以看到 for 迴圈中將條件設定成 `k < N - 1`，就是這個目的來的。
習題練習
---
### [Tutorial] 趕不完的作業 2
---
Source：https://oj.ntucpc.org/problems/99
就只是把 ++、+1 換成 L。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, L;
cin >> N >> L;
vector<long long> d(N);
for (int i = 0; i < N; i++) {
cin >> d[i];
}
sort(d.begin(), d.end());
long long t = 0;
int counts = 0;
for (int i = 0; i < N; i++) {
if (d[i] >= t + L) {
counts++;
t += L;
}
}
cout << counts;
return 0;
}
```
### 餐點順序
---
Source：https://oj.ntucpc.org/problems/713
一樣的套路，資料必定要先排序，然後這邊用到了前綴和，就是那個變數 sum。
（假設套範例測資1進去）如果只用 sum 作為輸出結果，最後只會得到 6，那個 6 只是表示最後一個人他所等的時間，而不是所有人的時間。
所以我們還要再加上 total 變數去對前綴和累計（把每個人所等的時間加起來：1+3+6）。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector <long long> A(N);
for (int i = 0; i < N; i++){
cin >> A[i];
}
sort(A.begin(), A.end());
long long sum = 0;
long long total = 0;
for (int i = 0; i < N; i++){
sum += A[i];
total += sum;
}
cout << total;
return 0;
}
```
### TOI 2009 第三題：書
---
Source：https://zerojudge.tw/ShowProblem?problemid=b231
工廠內有 n 台裝訂機，但只有 1 台的印刷機，且印刷機同時只能印一本書。也就是說裝訂可以同時進行。
因為題目限制要先印刷再裝訂，所以為了降低印刷完成後累加的裝訂時間影響，裝訂時間比較長的書籍應儘早印刷。這樣可以讓裝訂階段開始得較早，從而降低其完成時間（自定義排序）。
由於題目給了兩個資料，一個是印刷時間，一個是裝訂時間，兩者是有關聯的，所以再次使用到了 pair 關聯式容器。
根據題目需求，是要先印刷再裝訂，所以下面的程式就先累計印刷時間（cumulativePrint 變數），再去求總耗時的最大值（ans）。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <pair<int, int>> t(n);
for (int i = 0; i < n; i++){
cin >> t[i].first >> t[i].second;
}
sort(t.begin(), t.end(), [](const pair<int, int>& a, const pair<int, int>& b){
return a.second > b.second;
});
int cumulativePrint = 0;
int ans = 0;
for (const auto &book : t) {
cumulativePrint += book.first;
ans = max(ans, cumulativePrint + book.second);
}
cout << ans;
return 0;
}
```
### Tasks and Deadlines
---
Source：https://cses.fi/problemset/task/1630
以能夠耗時最少的作業優先，然後就按照題目要求去做累加。記得 reward 也要累加哦。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector <pair<int, int>> tasks(n);
for (int i = 0; i < n; i++){
cin >> tasks[i].first >> tasks[i].second;
}
sort(tasks.begin(), tasks.end());
long long current_time = 0;
long long reward = 0;
for (const auto&task : tasks){
current_time += task.first;
reward += task.second - current_time;
}
cout << reward;
return 0;
}
```
Sign in with Wallet
Connect another wallet