Tham lam (1)
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Sort, pair và comparator
- Chủ đề
- sắp xếptham lam
- Trạng thái
Kiến thức cơ bản
Tham lam là gì
Gấu Po được phép lấy 3 hũ mật ong từ chiếc bàn đầy hũ to nhỏ khác nhau. Gấu Po không cần tính toán phức tạp: lần nào cũng chọn hũ to nhất còn lại trên bàn. Cách nghĩ "ở mỗi bước, chọn phương án tốt nhất ngay lúc này, chọn rồi thì không đổi ý" gọi là tham lam (greedy).
Ở các tuần trước, khi vét cạn hoặc quay lui, ta thử mọi khả năng rồi quay lại nếu sai. Tham lam thì khác: chỉ đi một đường duy nhất, mỗi phần tử chỉ xét một lần. Vì vậy chương trình chạy rất nhanh, thường chỉ tốn O(n log n) cho bước sắp xếp. Với n = 105, máy tính chỉ mất một cái chớp mắt.
Điều quan trọng cần nhớ: tham lam chỉ đúng khi cách chọn "tốt nhất" được chọn đúng. Tuần này ta làm quen với những bài tham lam chạy đúng. Tuần sau, ta sẽ gặp cả trường hợp tham lam bị "lừa" và học cách nhận ra chúng.
Ba bước giải bài tham lam
- Bước 1: Quyết định thế nào là "tốt nhất" (lớn nhất, nhỏ nhất, kết thúc sớm nhất,...).
- Bước 2: Sắp xếp dữ liệu theo tiêu chí đó (nếu cần).
- Bước 3: Duyệt từng phần tử theo thứ tự đã sắp. Chọn được thì chọn luôn, không quay lại sửa.
Dữ liệu --> Sắp xếp theo tiêu chí --> Duyệt từng phần tử
|-- chọn được --> chọn
|-- không được --> bỏ qua
(đã chọn thì KHÔNG đổi ý)
Bài toán 1: Đổi tiền ít tờ nhất
Gấu Po cần đổi N nghìn đồng ra tiền giấy với các mệnh giá 1, 2, 5, 10, 20, 50, 100, 200, 500 (mỗi loại có rất nhiều tờ). Muốn dùng ít tờ nhất, ta làm như khi trả tiền ở quầy: luôn lấy tờ có mệnh giá lớn nhất mà không vượt quá số tiền còn lại.
N = 1275
500 x 2 = 1000 còn 275
200 x 1 = 200 còn 75
50 x 1 = 50 còn 25
20 x 1 = 20 còn 5
5 x 1 = 5 còn 0 --> tổng cộng 6 tờ
#include <iostream>
using namespace std;
int main() {
int mg[] = {500, 200, 100, 50, 20, 10, 5, 2, 1};
long long n;
cin >> n;
long long soTo = 0;
for (int m : mg) {
soTo += n / m; // số tờ loại m
n %= m; // tiền còn lại
}
cout << soTo;
return 0;
}
Cách này đúng với hệ mệnh giá trên, và với mọi hệ mệnh giá mà mỗi mệnh giá đều là ước của mệnh giá lớn hơn nó (bài tự luyện số 1).
Bài toán 2: Chọn nhiều hoạt động nhất
Hội trường chỉ tổ chức được một hoạt động tại mỗi thời điểm. Có n hoạt động, hoạt động i diễn ra từ thời điểm s[i] đến e[i]. Hai hoạt động không chồng nhau nếu hoạt động này kết thúc lúc 5 và hoạt động kia bắt đầu lúc 5 (bắt đầu đúng lúc kia vừa kết thúc vẫn được). Hãy chọn được nhiều hoạt động nhất.
Có ba cách "chọn tốt nhất" nghe đều hợp lý. Em thử đoán xem cách nào luôn đúng nhé:
| Cách chọn | Ví dụ làm cách này sai | Kết quả |
|---|---|---|
| Hoạt động bắt đầu sớm nhất | [0,10], [1,2], [3,4] Chọn [0,10] trước thì chặn mất hai hoạt động còn lại | Chọn được 1, nhưng tối đa là 2 |
| Hoạt động ngắn nhất | [1,5], [4,6], [5,9] Chọn [4,6] (ngắn nhất) thì chặn mất cả hai hoạt động kia | Chọn được 1, nhưng tối đa là 2 ([1,5] và [5,9]) |
| Hoạt động kết thúc sớm nhất | Luôn đúng: kết thúc càng sớm thì càng chừa nhiều thời gian cho các hoạt động sau | Đúng |
Vậy tiêu chí là kết thúc sớm nhất. Ta sắp xếp các hoạt động theo thời điểm kết thúc tăng dần, rồi duyệt: hoạt động nào bắt đầu không sớm hơn mốc kết thúc của hoạt động vừa chọn thì chọn và cập nhật mốc.
Thời điểm 0 1 2 3 4 5 6 7 8 9
Việc 1 [1,2) [=) <-- chọn
Việc 2 [0,3)[=======) bỏ
Việc 3 [2,5) [=======) <-- chọn
Việc 4 [4,6) [====) bỏ
Việc 5 [5,8) [=======) <-- chọn
Việc 6 [7,9) [====) bỏ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(n); // {kết thúc, bắt đầu}
for (auto& p : v) {
int batDau, ketThuc;
cin >> batDau >> ketThuc;
p = {ketThuc, batDau};
}
sort(v.begin(), v.end());
int dem = 0, moc = 0; // moc: mốc kết thúc
for (auto& p : v) {
if (p.second >= moc) { // không chồng nhau
dem++;
moc = p.first; // mốc mới
}
}
cout << dem;
return 0;
}
Vì sao đúng? Giả sử có một cách chọn tối ưu mà hoạt động đầu tiên không phải là hoạt động kết thúc sớm nhất. Ta thay hoạt động đó bằng hoạt động kết thúc sớm nhất: các hoạt động sau vẫn không chồng nhau, số lượng hoạt động không giảm. Cách "thử đổi chỗ" này là mẹo hay để kiểm tra một cách chọn tham lam.
Một số công cụ hay dùng khi tham lam
| Công cụ | Công dụng |
|---|---|
| sort(v.begin(), v.end()) | Sắp xếp tăng dần. Với pair thì so sánh first trước, bằng nhau mới so sánh second, nên hãy đặt giá trị cần sắp xếp ở first |
| sort(v.begin(), v.end(), greater<int>()) | Sắp xếp giảm dần |
| sort(v.begin(), v.end(), cmp) | Sắp xếp theo tiêu chí tự đặt: hàm cmp(a, b) trả về true nếu a phải đứng trước b |
| Hai chỉ số l, r | Đặt l ở đầu, r ở cuối mảng đã sắp xếp để ghép cặp (nhỏ nhất với lớn nhất) |
| priority_queue<int, vector<int>, greater<int>> | Hộp luôn cho lấy ra số nhỏ nhất: top(), pop(), push() |
| long long | Tổng và tích dễ vượt quá 2·109, hãy dùng long long để không bị tràn số |
Nhận dạng bài tham lam
| Dạng bài | Tiêu chí "tốt nhất" | Cách làm |
|---|---|---|
| Đổi tiền (hệ mệnh giá chuẩn) | Tờ lớn nhất không vượt quá số tiền còn lại | Duyệt mệnh giá từ lớn đến nhỏ, dùng n / m và n %= m |
| Mua được nhiều món nhất với số tiền cho trước | Món rẻ nhất | Sắp xếp tăng dần, mua lần lượt đến khi hết tiền |
| Chọn nhiều hoạt động không chồng nhau | Kết thúc sớm nhất | Sắp xếp theo thời điểm kết thúc |
| Ghép cặp (bánh với bạn, người với thuyền) | Ghép nhỏ nhất với lớn nhất, hoặc ghép "vừa đủ" | Sắp xếp rồi dùng hai chỉ số l, r |
| Gộp nhiều lần (nối dây) | Luôn lấy hai phần tử nhỏ nhất | priority_queue lấy số nhỏ nhất |
| Xếp thứ tự công việc | Việc nhanh làm trước (hoặc theo tỉ lệ) | Sắp xếp với hàm so sánh cmp |
Luyện tập
Bài 1. Đổi tiền lẻ
Gấu Po bán mật ong được N nghìn đồng và muốn đổi ra tiền giấy mang về. Các tờ tiền có mệnh giá 1, 2, 5, 10, 20, 50, 100, 200, 500 (nghìn đồng), mỗi loại có rất nhiều tờ. Hãy giúp Gấu Po tìm số tờ tiền ít nhất để có đúng N nghìn đồng.
| Đầu vào | Một số nguyên N (1 ≤ N ≤ 109). | |
|---|---|---|
| Đầu ra | Số tờ tiền ít nhất. | |
| Test | Input | Output |
| 1 | 1275 | 6 |
| 2 | 2024 | 7 |
Bài 2. Thỏ đi chợ
Thỏ có M nghìn đồng đi chợ cà rốt. Chợ có n món, món thứ i có giá a[i] nghìn đồng và mỗi món chỉ mua được một lần. Thỏ muốn mua được nhiều món nhất. Hỏi Thỏ mua được tối đa bao nhiêu món?
| Đầu vào | Dòng 1: hai số nguyên n, M (1 ≤ n ≤ 105; 1 ≤ M ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số món nhiều nhất Thỏ mua được (in 0 nếu không đủ tiền mua món nào). | |
| Test | Input | Output |
| 1 | 5 20 6 3 9 4 8 | 3 |
| 2 | 3 5 7 8 9 | 0 |
Bài 3. Xếp hàng chờ khám
Phòng khám của bác sĩ Hổ có n bệnh nhân, bệnh nhân thứ i cần t[i] phút để khám. Bác sĩ khám lần lượt từng người. Thời gian chờ của một bệnh nhân là tổng thời gian khám của tất cả những người đứng trước họ (người đầu tiên chờ 0 phút). Hãy sắp xếp thứ tự khám để tổng thời gian chờ của tất cả bệnh nhân là nhỏ nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên t[i] (1 ≤ t[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng thời gian chờ nhỏ nhất. | |
| Test | Input | Output |
| 1 | 4 6 2 8 3 | 18 |
| 2 | 1 10 | 0 |
Bài 4. Chia bánh
Gấu Po có n bạn nhỏ, bạn thứ i chỉ vui khi nhận được chiếc bánh nặng ít nhất g[i] gam. Gấu Po có m chiếc bánh, chiếc thứ j nặng s[j] gam. Mỗi bạn nhận nhiều nhất một chiếc bánh, mỗi chiếc bánh chỉ được cho nhiều nhất một bạn. Hỏi có nhiều nhất bao nhiêu bạn được vui?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên g[i] (1 ≤ g[i] ≤ 109). Dòng 3: m số nguyên s[j] (1 ≤ s[j] ≤ 109). | |
|---|---|---|
| Đầu ra | Số bạn vui nhiều nhất. | |
| Test | Input | Output |
| 1 | 3 2 1 2 3 1 1 | 1 |
| 2 | 4 5 5 1 3 2 2 4 1 5 1 | 4 |
Bài 5. Hội trường vui chơi
Hội trường của trường chỉ tổ chức được một hoạt động tại mỗi thời điểm. Có n hoạt động đăng ký, hoạt động thứ i diễn ra từ thời điểm s[i] đến thời điểm e[i]. Hai hoạt động không chồng nhau nếu hoạt động này kết thúc cùng lúc hoạt động kia bắt đầu. Hãy chọn nhiều hoạt động nhất để tổ chức.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng sau, mỗi dòng gồm hai số nguyên s[i], e[i] (0 ≤ s[i] < e[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số hoạt động nhiều nhất có thể tổ chức. | |
| Test | Input | Output |
| 1 | 6 1 4 3 5 0 6 5 7 3 9 8 11 | 3 |
| 2 | 3 1 3 3 6 6 9 | 3 |
Bài 6. Thuyền cứu hộ
Sau trận lũ, Hổ lái thuyền đi cứu n bạn thú trên đảo, bạn thứ i nặng w[i] kg. Mỗi chiếc thuyền chở được tối đa 2 bạn và tổng cân nặng không vượt quá L kg (mỗi bạn đều nhẹ hơn hoặc bằng L kg nên luôn có thuyền chở được). Hỏi cần ít nhất bao nhiêu chiếc thuyền?
| Đầu vào | Dòng 1: hai số nguyên n, L (1 ≤ n ≤ 105; 1 ≤ L ≤ 109). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ L). | |
|---|---|---|
| Đầu ra | Số thuyền ít nhất. | |
| Test | Input | Output |
| 1 | 5 100 70 50 80 30 40 | 3 |
| 2 | 4 50 50 50 50 50 | 4 |
Bài 7. Trạm xăng trên đường
Gấu Po lái xe từ vị trí 0 đến vị trí D (tính bằng km) trên một đường thẳng. Bình xăng đầy chạy được K km. Xe xuất phát với bình đầy. Dọc đường có m trạm xăng, mỗi trạm ở một vị trí cho trước, và mỗi lần dừng ở trạm Gấu Po đổ đầy bình. Hỏi Gấu Po phải dừng đổ xăng ít nhất bao nhiêu lần để đến đích? Nếu không thể đến đích, in -1.
| Đầu vào | Dòng 1: ba số nguyên D, K, m (1 ≤ D, K ≤ 109; 0 ≤ m ≤ 105). Dòng 2: m vị trí trạm xăng theo thứ tự tăng dần, mỗi vị trí p thỏa 0 < p < D (nếu m = 0 thì không có dòng này). | |
|---|---|---|
| Đầu ra | Số lần dừng đổ xăng ít nhất, hoặc -1 nếu không thể đến đích. | |
| Test | Input | Output |
| 1 | 100 40 4 30 50 70 90 | 2 |
| 2 | 100 30 3 20 40 80 | -1 |
Bài 8. Nối dây thừng
Gấu Po có n sợi dây thừng, sợi thứ i dài l[i]. Nối hai sợi lại thành một sợi dài bằng tổng chiều dài hai sợi đó và tốn công sức đúng bằng chiều dài mới. Gấu Po muốn nối tất cả thành một sợi duy nhất. Tổng công sức nhỏ nhất là bao nhiêu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên l[i] (1 ≤ l[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng công sức nhỏ nhất (nếu n = 1 thì in 0). | |
| Test | Input | Output |
| 1 | 4 4 3 2 6 | 29 |
| 2 | 1 7 | 0 |
Bài 9. Giữ lại số lớn nhất
Hổ viết số nguyên dương N gồm d chữ số lên d tấm thẻ xếp thành một hàng. Hổ phải bỏ đi đúng k tấm thẻ, các thẻ còn lại giữ nguyên thứ tự. Hãy giúp Hổ bỏ thẻ sao cho số tạo thành là lớn nhất có thể.
| Đầu vào | Dòng 1: hai số nguyên d, k (1 ≤ d ≤ 105; 0 ≤ k < d). Dòng 2: xâu gồm d chữ số, chữ số đầu tiên khác 0. | |
|---|---|---|
| Đầu ra | Số lớn nhất sau khi bỏ đúng k chữ số. | |
| Test | Input | Output |
| 1 | 7 3 1432219 | 4329 |
| 2 | 5 2 91820 | 982 |
Bài tập tự luyện
Bài 1. Hệ tiền đảo Gấu
Trên đảo Gấu dùng n loại tiền xu có mệnh giá c[1] < c[2] < ... < c[n], trong đó c[1] = 1 và mỗi mệnh giá là ước của mệnh giá lớn hơn nó liền sau (c[i] chia hết c[i+1]). Mỗi loại có rất nhiều đồng. Hãy tìm số đồng xu ít nhất để trả đúng N.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 60). Dòng 2: n số nguyên c[i] (1 ≤ c[i] ≤ 1018). Dòng 3: số nguyên N (1 ≤ N ≤ 1018). | |
|---|---|---|
| Đầu ra | Số đồng xu ít nhất. | |
| Test | Input | Output |
| 1 | 4 1 5 25 125 1000 | 8 |
| 2 | 3 1 10 100 99 | 18 |
Bài 2. Đổi dấu K lần
Thỏ có n tấm thẻ, mỗi thẻ ghi một số nguyên (có thể âm). Thỏ phải làm đúng K lần thao tác sau: chọn một tấm thẻ bất kỳ và đổi dấu số trên thẻ đó (thẻ đã đổi dấu vẫn được chọn lại). Hãy giúp Thỏ làm cho tổng các số trên thẻ lớn nhất có thể.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n, K ≤ 105). Dòng 2: n số nguyên a[i] (-104 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng lớn nhất sau đúng K lần đổi dấu. | |
| Test | Input | Output |
| 1 | 5 3 -2 -1 3 4 -6 | 16 |
| 2 | 3 4 -5 2 3 | 6 |
Bài 3. Ghép số lớn nhất
Hổ có n tấm bìa, mỗi tấm ghi một số nguyên không âm. Hổ nối các số lại cạnh nhau theo một thứ tự tùy ý để tạo thành một số thật lớn. Ví dụ với các số 3, 30, 34 thì xếp 34, 3, 30 cho số 34330 là lớn nhất. Hãy in ra số lớn nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số lớn nhất tạo được, in dưới dạng một xâu (nếu tất cả các số đều bằng 0 thì in 0). | |
| Test | Input | Output |
| 1 | 5 3 30 34 5 9 | 9534330 |
| 2 | 3 0 0 0 | 0 |
Bài 4. Bắn bóng bay
Trên bức tường có n quả bóng bay, quả thứ i phủ đoạn từ l[i] đến r[i] trên trục hoành. Một mũi tên bắn thẳng đứng tại hoành độ x sẽ làm nổ mọi quả bóng có l[i] ≤ x ≤ r[i]. Hổ cần bắn nổ tất cả bóng. Hỏi cần ít nhất bao nhiêu mũi tên?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng sau, mỗi dòng gồm hai số nguyên l[i], r[i] (1 ≤ l[i] ≤ r[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số mũi tên ít nhất. | |
| Test | Input | Output |
| 1 | 4 10 16 2 8 1 6 7 12 | 2 |
| 2 | 3 1 2 3 4 5 6 | 3 |
Bài 5. Phòng họp
Trường có n cuộc họp, cuộc họp thứ i diễn ra từ thời điểm s[i] đến e[i]. Hai cuộc họp cần hai phòng khác nhau nếu thời gian của chúng chồng nhau. Nếu một cuộc họp kết thúc đúng lúc cuộc họp khác bắt đầu thì hai cuộc họp có thể dùng chung một phòng. Hỏi cần ít nhất bao nhiêu phòng họp?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng sau, mỗi dòng gồm hai số nguyên s[i], e[i] (0 ≤ s[i] < e[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số phòng họp ít nhất. | |
| Test | Input | Output |
| 1 | 4 9 12 10 11 12 14 11 13 | 2 |
| 2 | 3 1 5 2 6 3 7 | 3 |
Bài 6. Ghép đội học nhóm
Lớp của Thỏ có 2n bạn, bạn thứ i có điểm học tập a[i]. Cô giáo chia 2n bạn thành n đội, mỗi đội đúng 2 bạn. Điểm của một đội là tổng điểm của hai bạn trong đội. Cô muốn chia sao cho điểm của đội cao nhất là nhỏ nhất có thể. Hãy in ra giá trị đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: 2n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Điểm nhỏ nhất có thể của đội cao điểm nhất. | |
| Test | Input | Output |
| 1 | 3 4 1 5 2 3 6 | 7 |
| 2 | 2 1 2 3 100 | 101 |
Bài 7. Thỏ về tổ
Trên một con đường thẳng có n chú thỏ đứng ở các vị trí a[1], ..., a[n] và n cái tổ ở các vị trí b[1], ..., b[n]. Mỗi chú thỏ phải chui vào một tổ, mỗi tổ chỉ chứa một chú thỏ. Quãng đường của một chú thỏ là khoảng cách từ vị trí của nó đến tổ nó chọn. Hãy tìm tổng quãng đường nhỏ nhất của tất cả các chú thỏ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). Dòng 3: n số nguyên b[i] (-109 ≤ b[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng quãng đường nhỏ nhất. | |
| Test | Input | Output |
| 1 | 3 1 5 9 8 2 4 | 3 |
| 2 | 2 0 10 10 0 | 0 |
Bài 8. Thứ tự làm bài tập
Hổ có n bài tập và làm lần lượt từng bài, không nghỉ giữa chừng. Bài thứ i cần t[i] phút. Nếu bài thứ i hoàn thành ở phút thứ C (tính từ lúc bắt đầu làm bài đầu tiên) thì Hổ bị trừ w[i] × C điểm. Hãy sắp xếp thứ tự làm bài để tổng điểm bị trừ là nhỏ nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng sau, mỗi dòng gồm hai số nguyên t[i], w[i] (1 ≤ t[i], w[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | Tổng điểm bị trừ nhỏ nhất. | |
| Test | Input | Output |
| 1 | 3 3 1 1 1 2 2 | 13 |
| 2 | 2 5 1 1 5 | 11 |
Bài 9. Thử thách (không bắt buộc): Hạn nộp bài
Thỏ có n bài tập, mỗi bài làm đúng 1 ngày và mỗi ngày làm nhiều nhất 1 bài. Các ngày được đánh số 1, 2, 3, ... Bài thứ i phải làm xong vào ngày thứ d[i] hoặc sớm hơn thì mới được p[i] điểm, làm muộn hơn thì không được điểm (có thể bỏ qua bài đó). Hãy giúp Thỏ lên kế hoạch để tổng điểm nhận được lớn nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng sau, mỗi dòng gồm hai số nguyên d[i], p[i] (1 ≤ d[i] ≤ 109; 1 ≤ p[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 5 2 100 1 19 2 27 1 25 3 15 | 142 |
| 2 | 3 1 5 1 7 1 3 | 7 |
- Gợi ý chung: Trước khi viết code, hãy làm tay một ví dụ nhỏ và tự hỏi: "Chọn như vậy có làm mất cơ hội tốt hơn về sau không?". Có thể thử đổi chỗ: nếu lời giải tối ưu không chọn phần tử mà tham lam chọn, đổi sang phần tử đó thì kết quả có tệ đi không? Khi sắp xếp theo hai tiêu chí, hãy nhớ pair so sánh first trước. Các tổng (thời gian chờ, tổng quãng đường, tổng điểm) rất dễ vượt quá giới hạn của int, hãy dùng long long. Tham lam không phải lúc nào cũng đúng, tuần sau chúng ta sẽ cùng tìm hiểu khi nào cần cẩn thận.