Tham lam trong thi đấu

Mức độ: Nâng cao

Tham lam là ở mỗi bước chọn cái trông có lợi nhất lúc đó, không quay lại sửa. Bài Thuật toán tham lam ở mục CTDL & Giải thuật đã giới thiệu ý tưởng và cho thấy tham lam có thể sai. Trong đề thi, cái khó không phải là viết chương trình (thường chỉ là sắp xếp rồi duyệt), mà là chọn đúng tiêu chí tham lam và biết vì sao nó đúng. Bài này trình bày ba dạng hay gặp và một cách kiểm tra tiêu chí: lập luận đổi chỗ.

Chọn nhiều đoạn không giao nhau

Có n cuộc họp, cuộc họp thứ i diễn ra từ s_i đến e_i. Một phòng chỉ tổ chức được một cuộc họp mỗi lúc (cuộc sau được bắt đầu đúng lúc cuộc trước kết thúc). Chọn được nhiều cuộc họp nhất là bao nhiêu?

Có ba tiêu chí nghe đều hợp lý: chọn cuộc bắt đầu sớm, cuộc ngắn, hay cuộc kết thúc sớm. Chỉ tiêu chí thứ ba luôn đúng:

Tiêu chí	Ví dụ làm tiêu chí sai
bắt đầu sớm	[0, 100], [1, 2], [3, 4]: chọn [0, 100] thì mất cả hai cuộc còn lại
ngắn	[0, 5], [4, 6], [5, 10]: chọn [4, 6] (dài 2) thì không chọn được thêm, còn chọn [0, 5] và [5, 10] được 2
kết thúc sớm	luôn đúng, lý do ở dưới

Vì sao chọn cuộc kết thúc sớm luôn đúng? Lấy một cách chọn tốt nhất bất kỳ, gọi cuộc đầu tiên của nó là X. Cuộc kết thúc sớm nhất là G, nên G kết thúc không muộn hơn X. Thay X bằng G: các cuộc còn lại bắt đầu sau khi X kết thúc, nên cũng bắt đầu sau khi G kết thúc, không cuộc nào bị chồng lên G. Cách chọn mới vẫn hợp lệ và vẫn có cùng số cuộc họp. Vậy luôn có một cách chọn tốt nhất bắt đầu bằng G. Bỏ G và các cuộc chồng lên G, lặp lại lập luận với phần còn lại.

Chương trình: sắp xếp theo thời điểm kết thúc, đi lần lượt, cuộc nào bắt đầu không sớm hơn thời điểm kết thúc của cuộc vừa chọn thì chọn.

Python

import sys
d = sys.stdin.read().split()
n = int(d[0])
cuoc_hop = [(int(d[1 + 2 * i]), int(d[2 + 2 * i])) for i in range(n)]
cuoc_hop.sort(key=lambda c: c[1])          # kết thúc sớm đứng trước
so_cuoc = 0
ket_thuc_cuoi = -10**18
for bat_dau, ket_thuc in cuoc_hop:
    if bat_dau >= ket_thuc_cuoi:
        so_cuoc += 1
        ket_thuc_cuoi = ket_thuc
print(so_cuoc)

C++

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

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> cuocHop(n);   // (kết thúc, bắt đầu) để sắp theo kết thúc
    for (auto &c : cuocHop) cin >> c.second >> c.first;
    sort(cuocHop.begin(), cuocHop.end());
    int soCuoc = 0;
    long long ketThucCuoi = -1e18;
    for (auto [ketThuc, batDau] : cuocHop) {
        if (batDau >= ketThucCuoi) {
            soCuoc++;
            ketThucCuoi = ketThuc;
        }
    }
    cout << soCuoc << "\n";
    return 0;
}

Sắp xếp theo tiêu chí: lập luận đổi chỗ

Nhiều bài yêu cầu xếp thứ tự n việc sao cho một tổng nào đó nhỏ nhất. Thử mọi thứ tự mất n! bước. Cách tìm thứ tự đúng: xét hai việc đứng cạnh nhau A rồi B, và hỏi đổi chỗ thành B rồi A thì tổng thay đổi thế nào.

Ví dụ: một máy làm n việc, việc i mất t_i phút, mỗi việc phải chờ tới khi làm xong. Tổng các thời điểm hoàn thành nhỏ nhất là bao nhiêu?

Xét A đứng ngay trước B, trước cả hai đã mất T phút. A xong lúc T + t_A, B xong lúc T + t_A + t_B. Nếu đổi chỗ thì B xong lúc T + t_B, A xong lúc T + t_B + t_A. Các việc khác không bị ảnh hưởng. So hai tổng:

Thứ tự	Tổng thời điểm xong của A và B
A rồi B	2T + 2tA + tB
B rồi A	2T + 2tB + tA

A rồi B tốt hơn khi t_A < t_B. Vậy trong cách xếp tốt nhất, việc ngắn hơn luôn đứng trước: sắp xếp tăng dần theo thời gian. Nếu có hai việc đứng cạnh nhau sai thứ tự, đổi chỗ chúng làm tổng giảm, nên cách xếp đó chưa tốt nhất.

Ba việc 3, 1, 2 xếp thành 1, 2, 3: các thời điểm xong là 1, 3, 6, tổng 10. Xếp theo thứ tự đề cho (3, 1, 2) thì là 3, 4, 6, tổng 13.

Cách so sánh hai việc cạnh nhau như vậy cho ra hàm so sánh dùng để sắp xếp. Với tiêu chí phức tạp hơn (ví dụ việc có trọng số w: so t_A × w_B với t_B × w_A), viết hàm so sánh riêng:

Python

from functools import cmp_to_key

def so_sanh(a, b):            # a, b là (thời gian, trọng số)
    trai = a[0] * b[1]        # đặt a trước b
    phai = b[0] * a[1]        # đặt b trước a
    return -1 if trai < phai else (1 if trai > phai else 0)

viec.sort(key=cmp_to_key(so_sanh))

C++

sort(viec.begin(), viec.end(), [](const pair<long long, long long> &a, const pair<long long, long long> &b) {
    return a.first * b.second < b.first * a.second;   // a đứng trước b khi tốt hơn
});

Lưu ý: so sánh bằng phép nhân chéo thay vì chia t / w để tránh sai số số thực. Hàm so sánh trong C++ phải trả về false khi hai việc “bằng nhau” (dùng <, không dùng <=), nếu không sort có thể chạy sai.

Tham lam với hàng đợi ưu tiên

Có những bài không xếp được một lần là xong, mà phải chọn dần và sửa lại lựa chọn cũ. Khi đó dùng hàng đợi ưu tiên để luôn lấy ra được phần tử tốt nhất hoặc xấu nhất trong số đã chọn.

Ví dụ: n việc, mỗi việc làm trong 1 ngày, việc i phải xong trước hết ngày d_i và được p_i tiền. Mỗi ngày làm một việc. Được nhiều tiền nhất là bao nhiêu?

Đi các việc theo hạn chót tăng dần và tạm nhận mọi việc. Nếu số việc đã nhận vượt quá hạn chót d_i của việc đang xét, thì trong d_i ngày đầu không làm hết được: bỏ việc ít tiền nhất trong số đã nhận. Hàng đợi ưu tiên (lấy nhỏ nhất) cho biết việc đó ngay.

Việc (hạn, tiền)	Các việc đang nhận (tiền)	Ghi chú
(1, 20)	20
(2, 50)	20, 50
(2, 30)	50, 30	3 việc mà hạn chỉ 2 ngày, bỏ việc 20
(3, 10)	50, 30, 10

Tổng 90. Bỏ việc ít tiền nhất là đúng vì các việc đã nhận đều có hạn không muộn hơn d_i, bỏ việc nào cũng giải phóng một ngày như nhau, nên bỏ việc mất ít tiền nhất.

Python

import sys, heapq
d = sys.stdin.read().split()
n = int(d[0])
viec = sorted((int(d[1 + 2 * i]), int(d[2 + 2 * i])) for i in range(n))   # theo hạn chót
dang_nhan = []                     # tiền của các việc đang nhận, nhỏ nhất ở đầu
for han, tien in viec:
    heapq.heappush(dang_nhan, tien)
    if len(dang_nhan) > han:
        heapq.heappop(dang_nhan)   # bỏ việc ít tiền nhất
print(sum(dang_nhan))

C++

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

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> viec(n);   // (hạn chót, tiền)
    for (auto &v : viec) cin >> v.first >> v.second;
    sort(viec.begin(), viec.end());
    priority_queue<long long, vector<long long>, greater<long long>> dangNhan;
    long long tong = 0;
    for (auto [han, tien] : viec) {
        dangNhan.push(tien);
        tong += tien;
        if ((long long)dangNhan.size() > han) {
            tong -= dangNhan.top();
            dangNhan.pop();
        }
    }
    cout << tong << "\n";
    return 0;
}

Khi nào không dùng tham lam

Nghĩ ra một tiêu chí tham lam rất nhanh, nhưng tiêu chí sai thì mất điểm cả bài. Trước khi nộp:

• Thử tìm ví dụ phản chứng nhỏ (2, 3 phần tử) như bảng ở phần chọn đoạn.
• Viết chương trình vét cạn cho n nhỏ và stress test so với cách tham lam.
• Nếu lựa chọn ở bước này làm thay đổi những gì chọn được về sau theo cách khó so sánh (như bài toán cái túi với đồ vật không chia nhỏ được), thường phải dùng quy hoạch động.

Luyện tập

Gồm 17 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Chọn đoạn

Bài 1. Nhiều cuộc họp nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có s, e (0 ≤ s < e ≤ 10⁹): một cuộc họp từ thời điểm s đến thời điểm e. Phòng họp chỉ tổ chức một cuộc họp mỗi lúc, cuộc sau được bắt đầu đúng lúc cuộc trước kết thúc. In ra số cuộc họp nhiều nhất tổ chức được.

Ví dụ:

Nhập	In ra
5 1 4 3 5 0 6 5 7 8 9	3

Kiểm tra: nhập

10
0 3
2 5
4 7
6 9
1 2
3 4
8 10
5 6
9 11
7 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Hủy ít cuộc họp nhất

Dữ liệu như bài 1. Phải hủy một số cuộc họp để các cuộc còn lại tổ chức được trong một phòng. In ra số cuộc họp ít nhất phải hủy.

Ví dụ:

Nhập	In ra
5 1 4 3 5 0 6 5 7 8 9	2

Kiểm tra: nhập

10
0 10
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
0 2

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Ít điểm kiểm tra nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l < r ≤ 10⁹): một đoạn [l, r] gồm cả hai đầu. Chọn ít điểm nguyên nhất sao cho đoạn nào cũng chứa ít nhất một điểm đã chọn. In ra số điểm đó.

Ví dụ:

Nhập	In ra
4 1 3 2 5 4 6 7 8	3

Kiểm tra: nhập

8
0 4
1 2
3 6
5 9
2 3
7 8
6 7
10 12

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Phủ con đường

Dòng đầu có L và n (1 ≤ L ≤ 10⁹, 1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l < r ≤ 10⁹): một đèn chiếu sáng đoạn [l, r]. Chọn ít đèn nhất để cả đoạn [0, L] được chiếu sáng (hai đoạn chạm nhau ở một đầu là nối liền). In ra số đèn đó, hoặc -1 nếu không thể.

Ví dụ:

Nhập	In ra
10 4 0 4 2 7 5 10 3 6	3

Kiểm tra: nhập

20 8
0 5
1 8
4 9
7 13
8 12
12 16
13 20
15 19

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Tưới cây

Dòng đầu có n và k (1 ≤ n ≤ 2 × 10⁵, 0 ≤ k ≤ 10⁹), dòng thứ hai có vị trí x_i của n cây trên một hàng (0 ≤ x_i ≤ 10⁹). Một vòi đặt ở vị trí p tưới được mọi cây trong đoạn [p, p + k]. In ra số vòi ít nhất để tưới hết các cây.

Ví dụ:

Nhập	In ra
6 3 7 1 5 11 2 6	3

Kiểm tra: nhập

10 4
3 9 14 0 20 8 15 25 4 19

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Sắp xếp theo tiêu chí

Bài 6. Tổng thời gian chờ

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có t₁, …, t_n (1 ≤ t_i ≤ 10⁴): thời gian làm từng việc. Một máy làm lần lượt các việc theo thứ tự tùy chọn, bắt đầu từ thời điểm 0. In ra tổng nhỏ nhất của các thời điểm làm xong từng việc.

Ví dụ:

Nhập	In ra
3 3 1 2	10

Kiểm tra: nhập

8
7 2 9 4 4 1 8 3

Xem đáp số

122

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Việc quan trọng làm trước

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có t_i, w_i (1 ≤ t_i, w_i ≤ 10⁴): thời gian làm và mức quan trọng của việc i. Một máy làm lần lượt các việc từ thời điểm 0; việc i xong ở thời điểm C_i thì bị phạt w_i × C_i. In ra tổng tiền phạt nhỏ nhất.

Ví dụ:

Nhập	In ra
3 3 1 1 2 2 5	22

Kiểm tra: nhập

7
4 3
2 1
6 6
1 1
3 5
5 2
2 4

Xem đáp số

223

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Ghép số lớn nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên không âm (mỗi số không quá 10⁹). Viết các số liền nhau theo thứ tự tùy chọn để được một số lớn nhất. In ra số đó (không có chữ số 0 thừa ở đầu).

Ví dụ:

Nhập	In ra
4 3 30 34 9	934330

Kiểm tra: nhập

7
12 121 5 56 0 9 98

Xem đáp số

998565121210

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hai máy

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có a_i, b_i (1 ≤ a_i, b_i ≤ 10⁴). Mỗi sản phẩm phải qua máy 1 trong a_i phút rồi mới qua máy 2 trong b_i phút. Mỗi máy làm một sản phẩm mỗi lúc, hai máy làm các sản phẩm theo cùng một thứ tự. In ra thời gian ít nhất để làm xong mọi sản phẩm.

Ví dụ:

Nhập	In ra
3 3 2 1 4 2 2	9

Kiểm tra: nhập

7
5 2
1 3
4 4
2 6
6 1
3 3
2 5

Xem đáp số

25

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Chia đội hai người

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có 2n số nguyên dương (mỗi số không quá 10⁹): sức mạnh của 2n bạn. Chia thành n đội, mỗi đội 2 bạn, sức mạnh đội bằng tổng của hai bạn. In ra giá trị nhỏ nhất có thể của sức mạnh đội mạnh nhất.

Ví dụ:

Nhập	In ra
3 5 1 8 3 9 2	10

Kiểm tra: nhập

4
7 3 12 1 9 4 10 6

Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Thuyền cứu hộ

Dòng đầu có n và C (1 ≤ n ≤ 2 × 10⁵, 1 ≤ C ≤ 10⁹), dòng thứ hai có cân nặng của n người (mỗi người nặng không quá C). Mỗi thuyền chở tối đa 2 người với tổng cân nặng không quá C. In ra số thuyền ít nhất để chở hết mọi người.

Ví dụ:

Nhập	In ra
5 10 9 2 5 5 8	3

Kiểm tra: nhập

9 100
60 40 85 15 50 50 30 70 95

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Tham lam với hàng đợi ưu tiên

Bài 12. Việc có hạn chót

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có d_i, p_i (1 ≤ d_i ≤ n, 1 ≤ p_i ≤ 10⁹). Việc i làm trong 1 ngày, phải xong trước khi hết ngày d_i thì được p_i tiền. Mỗi ngày làm một việc, bắt đầu từ ngày 1. In ra số tiền nhiều nhất.

Ví dụ:

Nhập	In ra
4 2 30 1 20 3 10 2 50	90

Kiểm tra: nhập

10
3 40
1 25
2 60
3 15
4 70
2 35
4 20
1 50
5 10
5 5

Xem đáp số

230

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Nối dây

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có độ dài của n đoạn dây (mỗi độ dài từ 1 đến 10⁹). Mỗi lần nối hai đoạn dài x và y thành một đoạn dài x + y tốn x + y đồng. Nối tới khi còn một đoạn. In ra tổng chi phí nhỏ nhất.

Ví dụ:

Nhập	In ra
4 4 3 2 6	29

Kiểm tra: nhập

6
8 1 5 3 9 2

Xem đáp số

65

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đổ xăng ít lần nhất

Dòng đầu có D, F, n (1 ≤ D ≤ 10⁹, 0 ≤ F ≤ 10⁹, 0 ≤ n ≤ 2 × 10⁵): xe đi từ vị trí 0 tới vị trí D, lúc đầu có F lít xăng, mỗi km tốn 1 lít, bình xăng chứa được bao nhiêu cũng được. n dòng sau mỗi dòng có x_i, g_i (0 < x_i < D, 1 ≤ g_i ≤ 10⁹): trạm ở vị trí x_i cho đổ g_i lít. In ra số lần dừng đổ xăng ít nhất, hoặc -1 nếu không tới được D.

Ví dụ:

Nhập	In ra
25 10 4 5 10 10 5 15 3 20 8	2

Kiểm tra: nhập

50 8 8
3 4
6 10
8 2
12 9
20 12
25 5
30 15
40 6

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Làm kịp nhiều việc nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n dòng sau mỗi dòng có t_i, d_i (1 ≤ t_i, d_i ≤ 10⁹): việc i làm trong t_i phút và phải xong không muộn hơn thời điểm d_i. Một máy làm lần lượt từ thời điểm 0. In ra số việc nhiều nhất làm kịp hạn (các việc không kịp thì bỏ, không làm).

Ví dụ:

Nhập	In ra
4 2 2 1 3 2 4 2 6	3

Kiểm tra: nhập

9
3 4
2 3
5 9
1 2
4 10
2 6
3 7
6 12
2 8

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 16. Xóa chữ số

Dòng đầu là số nguyên dương N gồm không quá 2 × 10⁵ chữ số, dòng thứ hai có k (0 ≤ k < số chữ số của N). Xóa đúng k chữ số của N (các chữ số còn lại giữ nguyên thứ tự) để được số nhỏ nhất. In ra số đó, bỏ các chữ số 0 ở đầu.

Ví dụ:

Nhập	In ra
1432219 3	1219

Kiểm tra: nhập

7053819264
4

Xem đáp số

19264

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Trả tiền ít tờ nhất

Tiền Việt Nam có các mệnh giá 1, 2, 5, 10, 20, 50, 100, 200, 500 (nghìn đồng). Cho N (1 ≤ N ≤ 10¹⁸), in ra số tờ tiền ít nhất để trả đúng N nghìn đồng (mỗi mệnh giá dùng bao nhiêu tờ cũng được).

Ví dụ: nhập 380 thì in ra 5.

Kiểm tra: nhập 98765.

Xem đáp số

201

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.