Greedy

Lấy tờ lớn nhất

Có các mệnh giá $c_1 < c_2 < \dots < c_k$ với $c_1 = 1$, mỗi mệnh giá dùng bao nhiêu tờ cũng được. Cần trả đúng $S$ đồng bằng ít tờ nhất. Quy tắc tham lam chỉ có một dòng: lấy tờ lớn nhất không vượt số tiền còn phải trả, rồi lặp lại. Với các mệnh giá $1, 3, 9, 27$ và $S = 50$, ta lấy $27$, hai tờ $9$, một tờ $3$, hai tờ $1$: 6 tờ.

Quy tắc gọn, nhưng gọn chưa phải đúng. Với các mệnh giá $1, 3, 4$ và $S = 6$, tham lam lấy $4 + 1 + 1$, tức 3 tờ, trong khi $3 + 3$ chỉ cần 2 tờ. Một phản ví dụ nhỏ bác bỏ cả quy tắc, nên tìm phản ví dụ là việc đầu tiên mỗi khi nghĩ ra một lời giải tham lam; chứng minh chỉ đáng viết cho quy tắc đã sống sót qua vài lần thử.

Một điều kiện đủ để quy tắc đúng: mỗi mệnh giá là bội của mệnh giá nhỏ hơn kề nó, $c_{j+1} = m_j c_j$. Chứng minh. Một cách trả tối ưu dùng ít hơn $m_j$ tờ $c_j$ với mỗi $j < k$, vì $m_j$ tờ ấy đổi được lấy một tờ $c_{j+1}$. Do đó các tờ nhỏ hơn $c_k$ gánh tổng không quá

nên số tờ $c_k$ phải đúng bằng thương nguyên S / c_k, chính là số tờ tham lam lấy. Phần còn lại S % c_k là bài toán cùng dạng với ít mệnh giá hơn.

Chứng minh này lộ ra hai mệnh đề đứng sau mọi lời giải tham lam đúng. (A) Có một nghiệm tối ưu chứa lựa chọn tham lam. (B) Sau khi chọn, phần còn lại là bài toán cùng dạng và nhỏ hơn. Công sức thường nằm ở (A). Điều kiện chia hết chỉ là điều kiện đủ: hệ $1, 2, 5, 10, 20, 50, \dots$ cũng cho tham lam đúng dù $2$ không chia hết $5$.

Ví dụRút Tiền Gọn Nhất

Đề. Máy chỉ có các mệnh giá $1, 5, 10, 20, 100$. Phát đúng $n \le 10^9$ đồng bằng ít tờ nhất.

Lời giải. Kiểm từng cặp mệnh giá kề nhau: $5 = 5 \cdot 1$, $10 = 2 \cdot 5$, $20 = 2 \cdot 10$, $100 = 5 \cdot 20$. Mỗi mệnh giá là bội của mệnh giá kề dưới, nên theo chứng minh trên tham lam đúng. Duyệt mệnh giá từ lớn xuống, lấy n / c tờ rồi giữ phần dư.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, c[] = {100, 20, 10, 5, 1};

signed main() {
    cin >> n;
    ll ans = 0;
    for (ll i = 0; i < 5; i++) {
        ans += n / c[i];
        n %= c[i];
    }
    cout << ans << '\n';
}

ChạyInput286

Output8

Chọn hoạt động

Có $n$ hoạt động, hoạt động $i$ diễn ra từ $s_i$ đến $e_i$. Mỗi lúc chỉ tham dự được một hoạt động và phải tham dự trọn vẹn; hoạt động mới được bắt đầu đúng lúc hoạt động trước kết thúc. Tham dự được nhiều nhất bao nhiêu hoạt động?

Chưa biết quy tắc nào đúng, ta nêu vài quy tắc rồi tìm phản ví dụ cho từng cái. Ba ứng viên: chọn hoạt động bắt đầu sớm nhất, ngắn nhất, hay kết thúc sớm nhất; chọn xong thì loại những hoạt động chồng lên nó.

Hoạt động bắt đầu sớm nhất có thể kéo dài tới mức chặn mọi hoạt động khác. Hoạt động ngắn nhất có thể vắt ngang hai hoạt động vốn ghép được với nhau: $[4, 7]$ chặn cả $[1, 5]$ lẫn $[6, 10]$. Quy tắc kết thúc sớm nhất thì không tìm được phản ví dụ nào.

Chứng minh bằng đổi chỗ. Gọi $G$ là hoạt động kết thúc sớm nhất, $O$ là một cách chọn tối ưu bất kỳ và $F$ là hoạt động đầu tiên trong $O$. Vì $G$ kết thúc không muộn hơn $F$, mọi hoạt động khác của $O$ bắt đầu không sớm hơn lúc $G$ kết thúc. Thay $F$ bằng $G$ cho một cách chọn hợp lệ, cùng số hoạt động, nay chứa $G$: đó là (A). Sau khi chọn $G$, các hoạt động còn dùng được là những hoạt động bắt đầu không sớm hơn lúc $G$ kết thúc: bài toán cùng dạng, tức (B).

Chứng minh chặt chẽ tốn thời gian, mà trong phòng thi bạn không có thừa. Cách rẻ nhất để biết một quy tắc có sai không là viết thêm vét cạn cho dữ liệu rất nhỏ rồi chạy cả hai trên vài chục nghìn test ngẫu nhiên. Chương trình dưới kiểm lại cả ba quy tắc trên, gồm bốn phần:

• key(i) là khóa sắp xếp của quy tắc đang thử: thời điểm kết thúc (rule = 0), bắt đầu (rule = 1) hay độ dài (rule = 2). cmp so hai chỉ số theo khóa đó.
• over(i, j) cho biết hai hoạt động có chồng nhau không: phần chung có độ dài dương khi mỗi hoạt động bắt đầu trước lúc hoạt động kia kết thúc. Dấu < chặt cho phép hoạt động sau bắt đầu đúng lúc hoạt động trước kết thúc.
• greedy() sắp chỉ số theo khóa rồi đi lần lượt, nhận hoạt động nào không chồng với mọi hoạt động đã nhận. brute() thử mọi tập con của tối đa 7 hoạt động và giữ tập lớn nhất không có cặp nào chồng nhau.
• main sinh 20000 bộ test ngẫu nhiên với $n \le 7$ và thời điểm trong $[1, 10]$, đếm số test mà hai bên cho kết quả khác nhau.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, rule, s[10], e[10], ord[10], pick[10];

ll key(ll i) {
    if (rule == 0) return e[i];
    if (rule == 1) return s[i];
    return e[i] - s[i];
}

bool cmp(ll i, ll j) {
    return key(i) < key(j);
}

bool over(ll i, ll j) {
    return s[i] < e[j] && s[j] < e[i];
}

ll greedy() {
    for (ll i = 0; i < n; i++) ord[i] = i;
    stable_sort(ord, ord + n, cmp);
    ll m = 0;
    for (ll k = 0; k < n; k++) {
        bool ok = true;
        for (ll t = 0; t < m; t++)
            if (over(ord[k], pick[t])) ok = false;
        if (ok) pick[m++] = ord[k];
    }
    return m;
}

ll brute() {
    ll best = 0;
    for (ll mask = 0; mask < (1 << n); mask++) {
        bool ok = true;
        for (ll i = 0; i < n; i++)
            for (ll j = i + 1; j < n; j++)
                if ((mask >> i & 1) && (mask >> j & 1) && over(i, j)) ok = false;
        if (ok) best = max(best, (ll)__builtin_popcount(mask));
    }
    return best;
}

signed main() {
    mt19937 rng(2024);
    string name[] = {"kết thúc sớm nhất", "bắt đầu sớm nhất", "ngắn nhất"};
    for (rule = 0; rule < 3; rule++) {
        ll wrong = 0;
        for (ll t = 1; t <= 20000; t++) {
            n = rng() % 7 + 1;
            for (ll i = 0; i < n; i++) {
                s[i] = rng() % 9 + 1;
                e[i] = s[i] + rng() % (10 - s[i]) + 1;
            }
            if (greedy() != brute()) wrong++;
        }
        cout << name[rule] << ": sai " << wrong << "/20000 test\n";
    }
}

Outputkết thúc sớm nhất: sai 0/20000 test
bắt đầu sớm nhất: sai 4709/20000 test
ngắn nhất: sai 102/20000 test

Quy tắc đúng không bị bắt lần nào, hai quy tắc sai bị bắt hàng trăm, hàng nghìn lần. Không bị bắt chưa phải là chứng minh, nhưng với test đủ nhỏ và đủ nhiều thì lỗi hiếm khi sống sót: phản ví dụ của quy tắc sai thường chỉ cần ba hoạt động.

Ví dụChọn Ca Tham Dự

Đề. $n \le 2 \cdot 10^5$ hoạt động $[a_i, b_i]$, được bắt đầu đúng lúc hoạt động trước kết thúc. Tham dự trọn vẹn được nhiều nhất bao nhiêu hoạt động?

Lời giải. Sắp theo thời điểm kết thúc tăng dần, giữ last là thời điểm kết thúc của hoạt động nhận gần nhất; nhận hoạt động nếu $a_i \ge$ last. Dấu >= vì đề cho bắt đầu đúng lúc kết thúc; nếu chạm đầu mút cũng tính là chồng thì phải dùng >. Sắp các cặp $(b_i, a_i)$ để sort mặc định xếp theo kết thúc. Cả bài $O(n \log n)$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n;
pair<ll, ll> p[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> p[i].second >> p[i].first;
    sort(p + 1, p + n + 1);
    ll last = 0, ans = 0;
    for (ll i = 1; i <= n; i++)
        if (p[i].second >= last) {
            ans++;
            last = p[i].first;
        }
    cout << ans << '\n';
}

ChạyInput6
1 4
3 5
4 7
5 6
6 9
7 8

Output3

Đổi chỗ hai việc kề

Nhiều bài tham lam không hỏi chọn gì mà hỏi làm theo thứ tự nào. Có $n!$ thứ tự, nhưng lời giải thường là sắp theo một khóa. Muốn tìm khóa, xét đúng hai phần tử đứng kề nhau và tính xem đổi chỗ chúng làm kết quả thay đổi bao nhiêu.

Bài toán: $n$ việc làm lần lượt trên một máy từ thời điểm $0$. Việc $i$ cần $p_i$ đơn vị thời gian, có trọng số $w_i$ và hoàn thành lúc $C_i$. Chọn thứ tự để tổng $w_1 C_1 + w_2 C_2 + \dots + w_n C_n$ nhỏ nhất.

Giả sử hai việc $X$ (cần $a$, trọng số $w_X$) và $Y$ (cần $b$, trọng số $w_Y$) đứng kề nhau, việc đứng trước bắt đầu lúc $T$. Dù thứ tự nào, cặp này cũng xong cùng lúc $T + a + b$, nên các việc khác giữ nguyên thời điểm. $X$ đứng trước thì cặp đóng góp $w_X (T + a) + w_Y (T + a + b)$; $Y$ đứng trước thì $w_Y (T + b) + w_X (T + a + b)$. Hiệu hai biểu thức, phần chứa $T$ triệt tiêu, còn

Hiệu không phụ thuộc $T$, nên đúng ở mọi chỗ trong lịch: $X$ nên đứng trước $Y$ khi $\frac{a}{w_X} \le \frac{b}{w_Y}$. Khóa là $p_i / w_i$, nhỏ đứng trước; khi mọi $w_i = 1$ khóa là $p_i$, việc ngắn làm trước. Nếu một thứ tự tối ưu chưa sắp theo khóa thì có hai việc kề nhau đứng ngược khóa; đổi chỗ chúng không làm tổng tăng, nên ta tới được thứ tự đã sắp mà vẫn tối ưu.

bool cmp(Job x, Job y) {
    return x.p * y.w < y.p * x.w;
}

So sánh bằng nhân chéo để khỏi chia, và dùng < chứ không dùng <=: hai việc cùng khóa thì cả hai chiều đều phải trả false. Cùng cách nghĩ cho bài hạn chót: nếu một lịch hợp lệ có $X$ ngay trước $Y$ mà hạn của $X$ muộn hơn, đổi chỗ thì $Y$ xong sớm hơn, còn $X$ xong đúng lúc $Y$ từng xong, vẫn kịp. Vậy sắp theo hạn chót tăng dần không làm hỏng lịch nào.

Ví dụTổng Thưởng Hoàn Thành

Đề. $n \le 2 \cdot 10^5$ việc làm lần lượt từ thời điểm $0$, việc $i$ cần $a_i$ và có mốc $d_i$. Hoàn thành lúc $f_i$ thì được thưởng $d_i - f_i$ (có thể âm). Phải làm tất cả; tìm tổng thưởng lớn nhất.

Lời giải. Tổng thưởng là tổng các $d_i$ trừ tổng các $f_i$. Tổng các $d_i$ không phụ thuộc thứ tự, nên bài thành cực tiểu hóa tổng thời điểm hoàn thành: trường hợp mọi trọng số bằng 1 của mục này, làm việc ngắn trước. Thời điểm tới $2 \cdot 10^{11}$, tổng tới cỡ $10^{17}$, cần long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n;
pair<ll, ll> job[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> job[i].first >> job[i].second;
    sort(job + 1, job + n + 1);
    ll now = 0, ans = 0;
    for (ll i = 1; i <= n; i++) {
        now += job[i].first;
        ans += job[i].second - now;
    }
    cout << ans << '\n';
}

ChạyInput4
3 10
1 7
2 9
4 20

Output26

Cái túi chia nhỏ

Có $n$ món, món $i$ nặng $w_i$ và giá trị $v_i > 0$; túi chứa tối đa $W$. Ở bản chia nhỏ được, ta được lấy một phần của món. Quy tắc: xếp các món theo $v_i / w_i$ giảm dần, lấy trọn món nếu còn chỗ, hết chỗ thì lấy phần vừa đủ.

Chứng minh đổi chỗ: gọi món $1$ là món có tỉ lệ cao nhất. Nếu một nghiệm tối ưu chưa lấy hết món $1$ thì túi đã đầy (còn chỗ thì thêm món $1$ chỉ có lợi), nên nó đang chứa một lượng món $j$ khác. Đổi một lượng $\delta > 0$ đủ nhỏ sang món $1$ thì giá trị thay đổi

Giữ nguyên dữ liệu nhưng cấm cắt món, tức bản nguyên khối (0/1), thì quy tắc vỡ. Với túi $9$ và các món $(w, v) = (4, 12), (6, 15), (2, 9), (5, 10)$, lấy theo tỉ lệ được $(2, 9)$ và $(4, 12)$, tổng $21$, rồi không món nào vừa $3$ chỗ còn lại; trong khi $(2, 9)$ cùng $(6, 15)$ cho $24$. Chứng minh vỡ đúng ở bước đổi một lượng $\delta$, vì món không cắt được. Túi nguyên khối giải bằng quy hoạch động (bài 12).

Xâu nhỏ nhất

Nhiều bài hỏi xâu nhỏ nhất (hay lớn nhất) theo thứ tự từ điển. Thứ tự từ điển quyết định ở vị trí khác nhau đầu tiên, nên chữ ở vị trí $1$ quan trọng hơn mọi chữ phía sau cộng lại. Tham lam tự nhiên là dựng kết quả từ trái sang phải, mỗi vị trí đặt chữ nhỏ nhất còn đặt được mà không làm hỏng khả năng hoàn thành phần sau.

Ví dụ: xóa đúng $k$ chữ số của xâu $s$ để xâu còn lại nhỏ nhất. Nếu chữ số $t$ đứng ngay trước chữ số $c$ nhỏ hơn nó, xóa $t$ thì $c$ tiến lên đúng vị trí của $t$ và xâu nhỏ đi ngay ở đó. Một ngăn xếp (stack: như chồng đĩa, chỉ thêm vào và lấy ra ở trên cùng, gọi là đỉnh; bài 09) làm cả việc trong một lượt: với mỗi chữ số $c$, chừng nào còn lượt xóa và đỉnh lớn hơn $c$ thì bỏ đỉnh, rồi đẩy $c$ vào; hết xâu mà còn lượt thì bỏ các chữ số cuối.

string st;
for (char c : s) {
    while (k > 0 && !st.empty() && st.back() > c) {
        st.pop_back();
        k--;
    }
    st.push_back(c);
}
st.resize(st.size() - k);

Với $s = 31415926$ và $k = 3$, ngăn xếp lần lượt là 3, 1, 14, 11, 115, 1159, 1152, 11526. Mỗi chữ số được đẩy vào và lấy ra tối đa một lần, cả bài $O(n)$.

Ví dụTrộn Hai Luồng Chữ Số

Đề. Xâu chữ số $s$, tổng độ dài các test không quá $3 \cdot 10^5$. Được đổi chỗ hai chữ số kề nhau nếu một chẵn một lẻ, bao nhiêu lần tùy ý. Tìm xâu nhỏ nhất theo thứ tự từ điển.

Lời giải. Hai chữ số cùng chẵn lẻ không bao giờ vượt qua nhau, nên thứ tự của các chữ số chẵn và của các chữ số lẻ được giữ nguyên; ngược lại, mọi cách trộn hai dãy ấy đều đạt được. Bài thành: trộn dãy chữ số chẵn $E$ và dãy chữ số lẻ $O$ (mỗi dãy giữ thứ tự) để được xâu nhỏ nhất. Xây từ trái sang phải: ở mỗi bước lấy chữ nhỏ hơn trong hai chữ đứng đầu $E$ và $O$. Hai chữ đầu khác chẵn lẻ nên không bao giờ bằng nhau, lựa chọn luôn rõ ràng; giống bước trộn của sắp xếp trộn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll t;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        string s, ev, od, ans;
        cin >> s;
        for (char c : s) {
            if ((c - '0') % 2 == 0) ev += c;
            else od += c;
        }
        ll i = 0, j = 0;
        while (i < (ll)ev.size() && j < (ll)od.size()) {
            if (ev[i] < od[j]) ans += ev[i++];
            else ans += od[j++];
        }
        ans += ev.substr(i) + od.substr(j);
        cout << ans << '\n';
    }
}

ChạyInput3
7092
86420
135024

Output0279
86420
012345

Chi phí trừ tiết kiệm

Một dạng tham lam hay gặp: tính chi phí khi chưa làm gì, rồi xem mỗi lựa chọn cho phép tiết kiệm bao nhiêu. Nếu các khoản tiết kiệm độc lập với nhau (chọn khoản này không làm khoản kia đổi giá trị) và chỉ được chọn tối đa $k$ khoản, thì chọn $k$ khoản lớn nhất là tối ưu: một cách chọn bỏ sót khoản $y$ mà lấy khoản $x < y$ thì đổi $x$ lấy $y$ chỉ có lợi. Việc khó là biến đề về dạng “các khoản độc lập”.

Ví dụ: hành lang có các ô cần che ở vị trí $b_1 < \dots < b_n$, dùng không quá $k$ tấm chắn, mỗi tấm phủ một đoạn ô liên tiếp; tổng độ dài nhỏ nhất là bao nhiêu? Một tấm duy nhất phủ từ $b_1$ đến $b_n$. Mỗi tấm thêm cho phép bỏ trống một khoảng giữa hai ô kề nhau, tiết kiệm $b_{i+1} - b_i - 1$ ô. Các khoảng rời nhau nên các khoản độc lập: bỏ $k - 1$ khoảng lớn nhất. Với $b = 2, 3, 12, 13, 14, 40$ và $k = 3$, một tấm tốn $39$, bỏ hai khoảng $25$ và $8$ còn $6$.

Hàng đợi ưu tiên

Có những bài mà lựa chọn tham lam ở mỗi bước làm thay đổi tập ứng viên: chọn xong thì có phần tử mới sinh ra, hoặc phần tử mới tới theo thời gian. Khi đó sắp một lần là không đủ; ta cần một cấu trúc luôn trả lại phần tử nhỏ nhất (hay lớn nhất) hiện có. Đó là hàng đợi ưu tiên (priority_queue): push, top, pop mỗi thao tác $O(\log n)$ (bài 09 nói kỹ hơn). Mặc định nó nhả phần tử lớn nhất; khai báo thêm greater<ll> thì nhả phần tử nhỏ nhất.

Ví dụCắt Thanh Theo Danh Sách

Đề. Thanh dài $x \le 10^9$ cần cắt thành đúng $n \le 2 \cdot 10^5$ đoạn dài $d_1, \dots, d_n$. Mỗi lần cắt một đoạn thành hai, chi phí bằng độ dài đoạn trước khi cắt. Tìm tổng chi phí nhỏ nhất.

Lời giải. Chạy ngược thời gian: bắt đầu với $n$ đoạn $d_i$, mỗi bước ghép hai đoạn thành một với chi phí bằng tổng của chúng, tới khi còn một thanh. Quy tắc: luôn ghép hai đoạn ngắn nhất đang có. Với $1, 2, 3, 4$: ghép $1 + 2$ (chi phí $3$), rồi $3 + 3$ (chi phí $6$), rồi $4 + 6$ (chi phí $10$), tổng $19$.

Vì sao đúng: vẽ các lần ghép thành sơ đồ như hình, mỗi đoạn ban đầu là một nút ở dưới cùng, mỗi lần ghép nối hai nút thành một nút mới phía trên. Đoạn $d_i$ nằm trong $h_i$ lần ghép thì độ dài của nó bị tính đúng $h_i$ lần, nên tổng chi phí là $d_1 h_1 + d_2 h_2 + \dots + d_n h_n$. Trong một cách ghép tối ưu, đổi chỗ đoạn ngắn nhất với đoạn nằm trong nhiều lần ghép nhất không làm tổng tăng, nên có cách ghép tối ưu mà hai đoạn ngắn nhất được ghép với nhau ngay từ lần đầu: đó là (A). Coi hai đoạn đó là một đoạn bằng tổng của chúng thì được bài cùng dạng ít hơn một đoạn: (B). Đây chính là mã Huffman. Mỗi lần ghép tốn tới $10^9$ mà có tới $2 \cdot 10^5$ lần, nên dùng long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll x, n;
priority_queue<ll, vector<ll>, greater<ll>> pq;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> x >> n;
    for (ll i = 1; i <= n; i++) {
        ll d;
        cin >> d;
        pq.push(d);
    }
    ll ans = 0;
    while (pq.size() > 1) {
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans << '\n';
}

ChạyInput10 4
1 2 3 4

Output19

Khi $n = 1$ vòng lặp không chạy và ta in $0$: thanh đã đúng độ dài cần. Quy tắc này khác với ghép dây chuyền từ ngắn tới dài: với $1, 1, 1, 1$ dây chuyền tốn $2 + 3 + 4 = 9$, còn ghép hai đoạn ngắn nhất cho $2 + 2 + 4 = 8$.

multiset cũng lấy được phần tử nhỏ nhất trong $O(\log n)$, nhưng mỗi phần tử là một nút cấp phát riêng trong cây, còn priority_queue chỉ là một mảng liền:

Cùng độ phức tạp, priority_queue nhanh hơn khoảng 4 lần. Chỉ cần lấy phần tử nhỏ nhất hay lớn nhất thì dùng nó; multiset để dành cho lúc cần xóa một phần tử bất kỳ hay tìm phần tử kế tiếp.