【C++】競程筆記（貪心法則、貪婪演算法）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

註：本篇筆記是作者本人腦子最燒的一篇。

貪婪演算法（greedy algorithm）

又稱貪心法則，最常見的例子就是排程問題。

貪婪演算法在每一步決策中選擇當前看似最好的選項，其核心在於追求「局部最優解」，而非保證「全局最優解」。

縮短一下句子，貪婪演算法就是每一步選目前最好的就對了。

若一道題目要得到全局最優解，則應該要考慮使用動態規劃（Dynamic Programming）演算法。

對，貪心法就這樣，剩下就是靠做題目去抓感覺，但是貪心法就跟動態規劃一樣鬼，題目可以給你出得很簡單很甜，有時候可以給你難到嚇嚇叫，做個題目想個一天還不一定想得出來（被這些題目蹂躪過的作者表示）。

[Tutorial] 好吃的蛋糕

Source：https://oj.ntucpc.org/problems/97

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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)$ 的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}

image

[Tutorial] 趕不完的作業

Source：https://oj.ntucpc.org/problems/98

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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。

image

誰先晚餐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

image

第一次交的時候 WA，發現我忘記這是 EOF，忘記加 “\n” XD。

這邊用到 STL 的 pair，因為有 $C{i}, E{i}$ ，兩者是有關聯的，所以用上了所謂的關聯式容器 pair。

然後 sort() 部分用到了 lambda 函數，原因是我覺得這樣比較省麻煩，寫成一般函數就長這樣（比較直觀一點）：

1
2
3
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
2
3
1 1
2 2
3 3

改成降序之後就是：

1
2
3
3 3
2 2
1 1

因為題目輸出要求算的是所有時間的加總（到最後一人吃完為止），所以可列下表：

第 i 人煮菜時間吃飯時間加總
1336
2527
3617

至於這個 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)$ 來說就夠用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}

image

自定義排序部分有個小細節，前面不是說比值大排前面，小的排後面嗎？但因為如果程式直接這樣除，會有浮點數誤差的問題存在，所以我們把它交叉相乘，就變成 $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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}

image

餐點順序

Source：https://oj.ntucpc.org/problems/713

一樣的套路，資料必定要先排序，然後這邊用到了前綴和，就是那個變數 sum。

（假設套範例測資1進去）如果只用 sum 作為輸出結果，最後只會得到 6，那個 6 只是表示最後一個人他所等的時間，而不是所有人的時間。

所以我們還要再加上 total 變數去對前綴和累計（把每個人所等的時間加起來：1+3+6）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}

image

TOI2009 第三題：書

Source：https://zerojudge.tw/ShowProblem?problemid=b231

工廠內有 n 台裝訂機，但只有 1 台的印刷機，且印刷機同時只能印一本書。也就是說裝訂可以同時進行。

因為題目限制要先印刷再裝訂，所以為了降低印刷完成後累加的裝訂時間影響，裝訂時間比較長的書籍應儘早印刷。這樣可以讓裝訂階段開始得較早，從而降低其完成時間（自定義排序）。

由於題目給了兩個資料，一個是印刷時間，一個是裝訂時間，兩者是有關聯的，所以再次使用到了 pair 關聯式容器。

根據題目需求，是要先印刷再裝訂，所以下面的程式就先累計印刷時間（cumulativePrint 變數），再去求總耗時的最大值（ans）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}

image

Tasks and Deadlines

Source：https://cses.fi/problemset/task/1630

以能夠耗時最少的作業優先，然後就按照題目要求去做累加。記得 reward 也要累加哦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}