Tham lam (2)
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Tham lam (1)
- Chủ đề
- sắp xếptham lam
- Trạng thái
Kiến thức cơ bản
Nhớ lại: tham lam là gì
Ở tuần trước, em đã gặp thuật toán tham lam (greedy): ở mỗi bước, ta chọn phương án trông tốt nhất ngay lúc đó và không bao giờ đổi ý. Giống như Gấu Po xếp mật ong vào giỏ: lấy hũ nhỏ nhất trước, rồi hũ nhỏ nhì, cho đến khi giỏ đầy.
Câu hỏi quan trọng nhất của tham lam là: "tốt nhất" nghĩa là gì? Mỗi bài có một tiêu chí riêng. Chọn đúng tiêu chí thì đáp án đúng, chọn sai tiêu chí thì đáp án sai. Tuần này, ta sẽ học cách chọn tiêu chí và nhìn ra khi nào tham lam không dùng được.
Khuôn "sắp xếp rồi tham lam"
Rất nhiều bài tham lam giải được theo ba bước:
- Bước 1: Tìm tiêu chí "tốt nhất" (nhỏ nhất, lớn nhất, kết thúc sớm nhất, ...).
- Bước 2: Sắp xếp dữ liệu theo tiêu chí đó bằng sort (dùng pair hoặc hàm so sánh nếu cần).
- Bước 3: Duyệt một lượt từ đầu đến cuối, phần tử nào chọn được thì chọn, không quay lại.
Độ phức tạp chủ yếu nằm ở bước sort, tức là O(n log n). Với n = 105, máy tính chỉ mất một cái chớp mắt.
Ví dụ 1: Gấu Po chất hũ mật lên xe
Xe của Gấu Po chở được tối đa W kg. Có n hũ mật, hũ thứ i nặng w[i] kg. Gấu Po muốn chở được nhiều hũ nhất. Muốn nhiều hũ thì phải lấy hũ nhẹ trước. Tiêu chí là "nhẹ nhất".
W = 10 kg, các hũ: 7 2 5 3
Bước 1 (sắp xếp tăng): 2 3 5 7
Bước 2 (duyệt, lấy nếu còn chỗ):
lấy 2 -> còn 8 kg
lấy 3 -> còn 5 kg
lấy 5 -> còn 0 kg
hũ 7 -> không vừa, dừng
Kết quả: 3 hũ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, W;
cin >> n >> W;
vector<int> w(n);
for (int i = 0; i < n; i++) cin >> w[i];
sort(w.begin(), w.end()); // tiêu chí: hũ nhẹ nhất lấy trước
int cnt = 0;
for (int i = 0; i < n; i++) {
if (W < w[i]) break; // hũ nhẹ nhất còn lại cũng không vừa -> dừng
W -= w[i];
cnt++;
}
cout << cnt;
return 0;
}
Ví dụ 2: Chọn đúng tiêu chí
Hổ quản lý một sân khấu. Có n tiết mục, tiết mục i diễn từ thời điểm l[i] đến r[i]. Hai tiết mục không được diễn chồng nhau (tiết mục này kết thúc đúng lúc tiết mục kia bắt đầu thì vẫn được). Hổ muốn xếp được nhiều tiết mục nhất.
Có ba tiêu chí nghe đều hợp lý. Em thử xem tiêu chí nào đúng:
| Tiêu chí | Ví dụ làm tiêu chí sai | Kết quả |
|---|---|---|
| Bắt đầu sớm nhất | [1, 10], [2, 3], [4, 5] | Chọn [1, 10] rồi hết chỗ: 1 tiết mục. Đúng phải là 2 ([2, 3] và [4, 5]). |
| Ngắn nhất | [1, 5], [4, 6], [5, 9] | Chọn [4, 6] làm cản cả hai tiết mục còn lại: 1 tiết mục. Đúng phải là 2 ([1, 5] và [5, 9]). |
| Kết thúc sớm nhất | Không tìm được ví dụ sai | Đúng. Tiết mục kết thúc sớm nhất để lại nhiều thời gian nhất cho các tiết mục sau. |
Để sort theo thời điểm kết thúc, ta lưu mỗi tiết mục thành pair {r, l}: sort sẽ xếp theo phần tử đầu tiên của pair, tức là r.
vector<pair<int, int>> v(n); // lưu {r, l} để sort theo r
for (auto& p : v) cin >> p.second >> p.first; // đọc l rồi r
sort(v.begin(), v.end());
int last = -1, cnt = 0; // last: thời điểm tiết mục vừa chọn kết thúc
for (auto& p : v) {
if (p.second >= last) { // l >= last: không chồng nhau
cnt++;
last = p.first; // cập nhật r mới
}
}
Ví dụ 3: Tự tạo tiêu chí bằng hàm so sánh
Có khi tiêu chí không phải là "nhỏ nhất" hay "lớn nhất" đơn giản. Gấu Po có các thẻ ghi số 9, 91, 5 và muốn ghép chúng thành một số lớn nhất. Nếu xếp theo giá trị giảm dần (91, 9, 5) thì được 9195, nhưng xếp 9, 91, 5 lại được 9915 lớn hơn. Vì "9" + "91" = "991" lớn hơn "91" + "9" = "919", nên thẻ 9 phải đứng trước thẻ 91.
Quy tắc: thẻ a đứng trước thẻ b nếu ghép "a rồi b" lớn hơn ghép "b rồi a". Ta viết hàm so sánh (đã học ở tuần 11):
bool cmp(const string& a, const string& b) {
return a + b > b + a; // a đứng trước b nếu "ab" lớn hơn "ba"
}
// sort(v.begin(), v.end(), cmp); rồi in lần lượt các chuỗi
Tham lam cũng có lúc sai
Tham lam chạy nhanh và code ngắn, nhưng không phải bài nào cũng dùng được. Hai ví dụ dưới đây "trông rất hợp lý" nhưng cho đáp án sai:
| Bài toán | Cách tham lam | Đáp án đúng |
|---|---|---|
| Máy đổi tiền có các tờ 1, 3, 4. Đổi 6 đồng ít tờ nhất. | Luôn lấy tờ lớn nhất còn được: 4 + 1 + 1 = 3 tờ. | 3 + 3 = 2 tờ. |
| Túi sức chứa 50 kg. Món A: 10 kg, 60 đồng. Món B: 20 kg, 100 đồng. Món C: 30 kg, 120 đồng. Mỗi món chỉ lấy nguyên một lần, muốn tổng giá trị lớn nhất. | Lấy món có giá trị trên mỗi kg lớn nhất trước: A (6), B (5) rồi C không còn vừa. Tổng 160 đồng. | Lấy B và C: 50 kg, 220 đồng. |
Với hệ tờ 1, 5, 10, 25 thì đổi tiền bằng tham lam lại đúng. Vì vậy, đừng tin tham lam chỉ vì nó "nghe có lý". Hãy tập ba câu hỏi:
- Tiêu chí sắp xếp của mình là gì, vì sao nó là tốt nhất?
- Mình đã thử với một ví dụ nhỏ cố tình "hiểm" chưa (như 1, 3, 4 ở trên)?
- Mình đã so với cách vét cạn (thử mọi cách, như quay lui ở tuần 24-25) trên dữ liệu nhỏ chưa? Nếu hai cách cho kết quả khác nhau thì tham lam sai.
Khi tham lam sai, em cần một cách khác mạnh hơn. Cách đó sẽ được học ở những tuần quy hoạch động.
Bảng tiêu chí hay gặp
| Dạng bài | Sắp xếp theo | Rồi làm gì |
|---|---|---|
| Mua, chở được nhiều món nhất | Giá (cân nặng) tăng dần | Cộng dần đến khi hết tiền (chỗ) |
| Tổng thời gian chờ nhỏ nhất | Thời gian phục vụ tăng dần | Cộng dồn thời gian chờ |
| Chọn nhiều tiết mục không chồng nhau | Thời điểm kết thúc tăng dần | Chọn nếu bắt đầu ≥ lần kết thúc trước |
| Ghép cặp (thuyền, bánh với bạn) | Sắp xếp, dùng hai con trỏ l, r | Ghép nhỏ nhất với lớn nhất, hoặc nhỏ nhất đủ dùng |
| Làm xong nhiều việc có hạn nộp | Hạn nộp tăng dần | Lấy việc, dùng priority_queue bỏ việc ít điểm nhất |
| Nối, hợp nhất hai thứ nhỏ nhất | Không sort một lần mà dùng priority_queue | Lấy hai nhỏ nhất, ghép, bỏ lại vào |
| Thứ tự ghép, thứ tự làm việc phức tạp | Tự viết hàm so sánh cmp | Duyệt theo thứ tự đó |
Luyện tập
Bài 1. Mua kẹo
Thỏ có M đồng để mua kẹo ở cửa hàng. Cửa hàng có n loại kẹo, mỗi loại chỉ còn một viên, viên thứ i giá a[i] đồng. Hỏi Thỏ mua được nhiều nhất bao nhiêu viên kẹo?
| Đầ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ố viên kẹo nhiều nhất Thỏ mua được. | |
| Test | Input | Output |
| 1 | 5 20 8 3 12 5 6 | 3 |
| 2 | 4 2 5 6 7 8 | 0 |
Bài 2. Hàng chờ nhận quà
Hổ phát quà cho n bạn xếp hàng nhận quà. Bạn thứ i cần t[i] phút để nhận quà. Mỗi bạn phải chờ cho đến khi tất cả các bạn đứng trước nhận xong. Hổ được phép sắp xếp lại thứ tự hàng. Tìm tổng thời gian chờ của tất cả các bạn nhỏ nhất có thể (thời gian chờ của một bạn là thời gian từ lúc bắt đầu cho đến khi bạn ấy bắt đầu được nhận quà).
| Đầ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 3 1 4 2 | 10 |
| 2 | 1 7 | 0 |
Bài 3. Chiếc thuyền cứu hộ
Gấu Po chèo thuyền cứu n bạn thú qua sông. Mỗi thuyền chở tối đa hai bạn và tổng cân nặng không quá W kg. Bạn thứ i nặng w[i] kg (w[i] ≤ W, nên bạn nào cũng đi được một mình). Hỏi cần ít nhất bao nhiêu chuyến thuyền?
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 105, 1 ≤ W ≤ 109). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ W). | |
|---|---|---|
| Đầu ra | Số chuyến thuyền ít nhất. | |
| Test | Input | Output |
| 1 | 5 100 20 80 50 50 70 | 3 |
| 2 | 3 10 6 6 6 | 3 |
Bài 4. Tiết mục sân khấu
Hổ có n tiết mục xin biểu diễn trên sân khấu, tiết mục i diễn từ thời điểm l[i] đến thời điểm r[i]. Hai tiết mục không được diễn chồng nhau; tiết mục này kết thúc đúng lúc tiết mục kia bắt đầu thì vẫn được. Hổ muốn chọn được nhiều tiết mục nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng hai số nguyên l[i], r[i] (0 ≤ l[i] < r[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số tiết mục nhiều nhất chọn được. | |
| Test | Input | Output |
| 1 | 5 1 3 2 5 3 6 6 8 5 9 | 3 |
| 2 | 3 1 10 2 5 6 9 | 2 |
Bài 5. Chia bánh quy
Gấu Po có n bạn và m cái bánh quy. Bạn thứ i chỉ hài lòng nếu nhận được bánh có kích cỡ ít nhất g[i]. Cái bánh thứ j có kích cỡ s[j]. Mỗi bạn nhận nhiều nhất một cái bánh, mỗi cái bánh cho nhiều nhất một bạn. Hỏi nhiều nhất bao nhiêu bạn được hài lòng?
| Đầ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 hài lòng nhiều nhất. | |
| Test | Input | Output |
| 1 | 4 3 1 2 3 4 2 2 3 | 3 |
| 2 | 2 3 5 6 1 2 3 | 0 |
Bài 6. Đổi dấu k lần
Thỏ có dãy n số nguyên. Thỏ bắt buộc phải thực hiện đúng k lần thao tác, mỗi lần chọn một số trong dãy (có thể chọn lại số đã chọn) rồi đổi dấu của nó. Hãy giúp Thỏ làm cho tổng của dãy lớn nhất có thể.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109). Dòng 2: n số nguyên a[i] (-104 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng lớn nhất của dãy sau đúng k lần đổi dấu. | |
| Test | Input | Output |
| 1 | 5 3 -2 0 5 -1 2 | 10 |
| 2 | 3 3 1 2 3 | 4 |
Bài 7. Nhân chéo nhỏ nhất
Gấu Po có hai dãy số nguyên dương a và b, mỗi dãy có n phần tử. Gấu Po được phép xếp lại thứ tự các phần tử của dãy b tùy ý (dãy a giữ nguyên). Sau đó Gấu Po tính tổng a[1]·b[1] + a[2]·b[2] + ... + a[n]·b[n]. Hãy tìm giá trị nhỏ nhất của tổng này.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 104). Dòng 3: n số nguyên b[i] (1 ≤ b[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Giá trị nhỏ nhất của tổng. | |
| Test | Input | Output |
| 1 | 3 1 3 5 2 4 6 | 28 |
| 2 | 1 7 9 | 63 |
Bài 8. Hàng bạn đồng đều
Cô giáo muốn chọn đúng k bạn trong lớp có n bạn để thành đội diễn văn nghệ, sao cho chiều cao các bạn chênh nhau ít nhất, tức là hiệu giữa chiều cao bạn cao nhất và bạn thấp nhất trong đội là nhỏ nhất. Hãy giúp cô tìm hiệu nhỏ nhất đó.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Hiệu nhỏ nhất giữa chiều cao lớn nhất và nhỏ nhất của k bạn được chọn. | |
| Test | Input | Output |
| 1 | 6 3 150 140 165 155 147 170 | 8 |
| 2 | 4 4 10 50 20 30 | 40 |
Bài 9. Máy đổi tiền "chỉ biết tham lam"
Máy đổi tiền ở siêu thị có k loại tờ. Máy luôn làm như sau: chọn tờ có mệnh giá lớn nhất không vượt quá số tiền còn lại, nhả ra, rồi lặp lại cho đến khi đủ số tiền S. Nếu đến lúc nào đó không có tờ nào nhỏ hơn hoặc bằng số tiền còn lại (mà số tiền còn lại chưa bằng 0) thì máy báo lỗi. Hãy cho biết máy nhả bao nhiêu tờ, hoặc báo lỗi.
| Đầu vào | Dòng 1: hai số nguyên k, S (1 ≤ k ≤ 5, 1 ≤ S ≤ 109). Dòng 2: k mệnh giá đôi một khác nhau, mỗi mệnh giá từ 1 đến 109, cho theo thứ tự bất kỳ. | |
|---|---|---|
| Đầu ra | Số tờ máy nhả ra, hoặc -1 nếu máy báo lỗi. | |
| Test | Input | Output |
| 1 | 4 63 1 5 10 25 | 6 |
| 2 | 3 6 1 3 4 | 3 |
Bài tập tự luyện
Bài 1. Số phòng họp ít nhất
Hổ tổ chức n buổi họp, buổi thứ i diễn ra từ l[i] đến r[i]. Hai buổi họp chồng nhau thì phải dùng hai phòng khác nhau; một buổi kết thúc đúng lúc buổi khác bắt đầu thì có thể dùng chung 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 tiếp theo: mỗi dòng hai số nguyên l[i], r[i] (0 ≤ l[i] < r[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số phòng họp ít nhất. | |
| Test | Input | Output |
| 1 | 5 1 4 2 5 4 7 6 9 5 8 | 3 |
| 2 | 3 1 2 2 3 3 4 | 1 |
Bài 2. Ghép thẻ số lớn nhất
Gấu Po có n thẻ, mỗi thẻ ghi một số tự nhiên. Gấu Po xếp các thẻ thành một hàng, đọc từ trái sang phải để được một số rất lớn (ghép các chữ số liền nhau). Hãy tìm số lớn nhất ghép được.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số tự nhiên (0 ≤ mỗi số ≤ 109). | |
|---|---|---|
| Đầu ra | Số lớn nhất ghép được (viết dưới dạng xâu; nếu toàn là chữ số 0 thì in 0). | |
| Test | Input | Output |
| 1 | 4 3 30 34 5 | 534330 |
| 2 | 3 0 0 0 | 0 |
Bài 3. Nối dây thừng
Hổ có n sợi dây thừng, sợi thứ i dài a[i]. Mỗi lần nối hai sợi dây thì tốn chi phí bằng tổng độ dài của hai sợi đó, và ta được một sợi mới. Hổ cần nối tất cả thành một sợi duy nhất. Hãy tìm tổng chi phí nhỏ nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng chi phí nhỏ nhất (nếu n = 1 thì in 0). | |
| Test | Input | Output |
| 1 | 4 4 3 2 6 | 29 |
| 2 | 1 10 | 0 |
Bài 4. Trạm xăng trên đường
Xe của Thỏ khởi hành từ vị trí 0 với bình xăng đầy, chạy được tối đa D km thì hết xăng. Đích đến ở vị trí L. Trên đường có m trạm xăng, trạm thứ i ở vị trí p[i] (0 < p[i] < L), vào trạm nào cũng được đổ đầy bình. Hỏi Thỏ phải dừng đổ xăng ít nhất bao nhiêu lần để đến được đích? Nếu không thể đến, in -1.
| Đầu vào | Dòng 1: ba số nguyên D, L, m (1 ≤ D, L ≤ 109, 0 ≤ m ≤ 105). Dòng 2: m số nguyên p[i] (không nhất thiết theo thứ tự). Nếu m = 0 thì dòng này trống. | |
|---|---|---|
| Đầu ra | Số lần đổ xăng ít nhất, hoặc -1. | |
| Test | Input | Output |
| 1 | 10 35 4 20 5 27 12 | 4 |
| 2 | 10 35 2 5 25 | -1 |
Bài 5. Tưới vườn
Mảnh vườn của Gấu Po là đoạn thẳng từ 0 đến L. Có n vòi nước, vòi thứ i tưới được đoạn từ l[i] đến r[i]. Gấu Po muốn mở ít vòi nhất sao cho cả đoạn từ 0 đến L đều được tưới (hai đoạn chạm đầu nhau vẫn tính là liền). Nếu không thể tưới hết, in -1.
| Đầu vào | Dòng 1: hai số nguyên L, n (1 ≤ L ≤ 109, 1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng hai số nguyên l[i], r[i] (0 ≤ l[i] < r[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số vòi ít nhất, hoặc -1. | |
| Test | Input | Output |
| 1 | 10 4 0 4 3 7 6 10 2 5 | 3 |
| 2 | 10 2 0 4 5 10 | -1 |
Bài 6. Làm bài tập đúng hạn
Thỏ có n bài tập, bài thứ i cần t[i] phút để làm và có hạn nộp là phút thứ d[i] (tính từ lúc Thỏ bắt đầu làm). Thỏ làm lần lượt từng bài, không nghỉ, không làm xen kẽ. Nếu bài i xong ở phút c[i] thì độ trễ của bài đó là max(0, c[i] - d[i]). Thỏ được chọn thứ tự làm bài, hãy tìm độ trễ lớn nhất nhỏ nhất có thể.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng hai số nguyên t[i], d[i] (1 ≤ t[i] ≤ 104, 1 ≤ d[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Độ trễ lớn nhất nhỏ nhất có thể (0 nếu có cách làm xong tất cả đúng hạn). | |
| Test | Input | Output |
| 1 | 3 4 4 3 5 2 6 | 3 |
| 2 | 2 2 10 3 5 | 0 |
Bài 7. Thứ tự việc của Hổ
Hổ có n việc cần làm lần lượt, không nghỉ. Việc thứ i mất t[i] phút và có "độ sốt ruột" w[i]. Nếu việc i xong ở phút c[i] thì Hổ mất w[i]·c[i] điểm kiên nhẫn. Hổ muốn chọn thứ tự làm việc để tổng điểm kiên nhẫn mất đi nhỏ nhất. Hãy tìm giá trị nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng hai số nguyên t[i], w[i] (1 ≤ t[i], w[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | Tổng điểm kiên nhẫn mất đi nhỏ nhất (dùng long long). | |
| Test | Input | Output |
| 1 | 3 3 1 1 2 2 4 | 20 |
| 2 | 2 5 1 1 1 | 7 |
Bài 8. Bài tập có hạn nộp
Thỏ có n bài tập, mỗi ngày làm được đúng một bài. Bài thứ i phải làm xong trong ngày thứ d[i] hoặc sớm hơn (ngày được tính từ 1), và nếu làm kịp sẽ được p[i] điểm. Bài nào không làm thì không được điểm. Hãy giúp Thỏ có tổng điểm lớn nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng 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 9 1 7 | 9 |
Bài 9. Thử thách (không bắt buộc): Tham lam đúng hay sai?
Với một hệ tờ tiền và số tiền S, hãy so sánh hai con số: số tờ theo cách tham lam (luôn lấy tờ lớn nhất còn được) và số tờ ít nhất thật sự có thể dùng (nghĩ cách thử mọi tổ hợp, ví dụ bằng quay lui). Hệ tờ luôn có tờ mệnh giá 1 nên luôn đổi được.
| Đầu vào | Dòng 1: hai số nguyên k, S (1 ≤ k ≤ 5, 1 ≤ S ≤ 100). Dòng 2: k mệnh giá đôi một khác nhau, mỗi mệnh giá từ 1 đến S; trong đó có mệnh giá 1. | |
|---|---|---|
| Đầu ra | Dòng 1: hai số: số tờ theo tham lam và số tờ ít nhất. Dòng 2: in DUNG nếu hai số bằng nhau, ngược lại in SAI. | |
| Test | Input | Output |
| 1 | 4 63 1 5 10 25 | 6 6 DUNG |
| 2 | 3 6 1 3 4 | 3 2 SAI |
| 3 | 3 30 1 10 25 | 6 3 SAI |
- Gợi ý chung: Trước khi viết code, hãy tự hỏi: "tiêu chí sắp xếp của mình là gì và vì sao nó đúng?". Nếu chưa chắc, hãy thử với một ví dụ nhỏ và nghĩ cách xếp khác.
Nhớ: Tổng có thể lớn hơn 2·109 (ví dụ tổng thời gian chờ, chi phí nối dây, tổng điểm kiên nhẫn) nên phải dùng long long. Lỗi hay gặp là khai int cho biến tổng.
Hàm so sánh: trong cmp chỉ dùng < hoặc > (không dùng <=, >=). Dùng <= có thể làm chương trình sai hoặc báo lỗi runtime khi dữ liệu có phần tử bằng nhau.
Kiểm tra bằng vét cạn: với bài tham lam em chưa chắc đúng, hãy viết thêm một chương trình thử mọi cách (hoán vị, tập con, quay lui) cho n nhỏ rồi so kết quả. Nếu có một bộ test hai chương trình cho kết quả khác nhau, tham lam của em đang sai tiêu chí.