¶ Tham lam
Người viết:
- Nguyễn Hoàng Dương - Trường Đại học Công nghệ, ĐHQG-HN.
Reviewer:
- Đoàn Quang Huy - Trường THPT Chuyên Nguyễn Tất Thành, Quảng Ngãi.
- Nguyễn Minh Nhật - Georgia Institute of Technology.
- Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
¶ Giới thiệu
Tham lam là một ý tưởng cơ bản và phổ biến trong giải thuật và lập trình, chủ yếu trong việc giải các bài toán tối ưu hoá. Ở mỗi bước chạy, thuật toán tham lam sẽ luôn chọn lựa chọn "tốt nhất" hiện tại (theo tiêu chí người thiết kế giải thuật đề ra), và không xét đến ảnh hưởng của nó đến những lựa chọn tiếp theo.
Từ những bài dễ cho đến rất khó, trong bất cứ một bước suy luận nào của bài toán, đều có thể xuất hiện tư tưởng tham lam. Điều quan trọng nhất khi áp dụng tham lam vào lời giải, là chứng minh được tính đúng đắn của quy luật tham lam -- đây thường là phần khó và tinh tế nhất, đòi hỏi kinh nghiệm, khả năng suy luận và sự nhạy bén.
Fun fact
Chứng minh bằng thực nghiệm (proof by AC): Trong thi đấu (đặc biệt trong ICPC), nếu ý tưởng tham lam là đủ ngắn, đủ đơn giản và ta tin rằng nó đúng (hoặc nghĩ mãi vẫn không tìm ra cách để nó sai) thì ta sẽ code luôn và chứng minh bằng việc có AC hay không.
Trong bài viết này, ở mỗi mục có các phần Ví dụ và Bài tập. Đối với các phần Bài tập, các bạn hãy cố gắng suy nghĩ thật kỹ và thử giải bài tập trước khi đọc lời giải.
¶ Những ý tưởng tham lam cơ bản
¶ Nguyên lý cực hạn
Đặc điểm chính của tham lam là nguyên lý cực hạn: lời giải tối ưu thường sẽ nằm ở các trường hợp biên, hoặc một nhóm nhỏ các trường hợp đặc biệt. Cách làm việc tự nhiên nhất là liệt kê một vài chiến lược ứng với các trường hợp biên đó, rồi tìm phản ví dụ để loại dần. Chiến lược nào sống sót thì ta mới tìm cách chứng minh.
¶ Ví dụ: Movie Festival - CSES
Cho bộ phim, mỗi bộ phim kéo dài từ thời điểm đến . Bạn có thể xem được trọn vẹn nhiều nhất bao nhiêu bộ phim ?
Ta thử nghĩ một số trường hợp biên như vậy:
- Luôn chọn bộ phim bắt đầu sớm nhất. Ở đây ta sẽ chọn A, rồi chọn D, rồi chọn E.
- Luôn chọn bộ phim ngắn nhất, nếu có nhiều bộ phim ngắn nhất thì chọn bộ phim bắt đầu sớm hơn. Ở đây ta sẽ chọn bộ phim C, rồi đến A, rồi đến B.
- Luôn chọn bộ phim kết thúc sớm nhất. Ở đây ta sẽ chọn 3 bộ phim C, rồi đến D, rồi đến E.
Lời giải và chứng minh
Dưới đây là phản ví dụ cho 2 trường hợp 1 và 2:
Ở chiến lược 1, khi xem bộ phim bắt đầu sớm nhất, nó hoàn toàn có thể dài đến mức đè hết lên các bộ phim còn lại, còn ở chiến lược 2, nếu bộ phim ngắn nhất ấy giao nhau với quá nhiều bộ phim khác, thì cũng khiến lựa chọn không tối ưu. Việc xét trường hợp cẩn thận, tự phản biện và tìm ra phản ví dụ là một kĩ năng quan trọng khi tiếp cận bài toán bằng tham lam.
Chiến lược thứ 3 là lời giải đúng cho bài toán cổ điển này.
Thật vậy, xét thời điểm ta đang chọn bộ phim tiếp theo, và gọi là bộ phim kết thúc sớm nhất trong số các bộ phim còn có thể xem. Giả sử một lời giải nào đó chọn bộ phim , tức kết thúc muộn hơn . Nếu ta có thể chọn một bộ phim để xem sau , thì bộ phim đó cũng có thể xem sau , bởi vì kết thúc trước. Do đó, tập hợp các bộ phim có thể xem sau là một tập con của các bộ phim có thể xem sau : thay bằng trong lời giải đó, ta được một lời giải không ít phim hơn. Hay nói cách khác, luôn tồn tại một lời giải tối ưu bắt đầu bằng .
Sau khi chọn , bài toán còn lại trên các bộ phim bắt đầu sau khi kết thúc có đúng dạng của bài toán ban đầu, nên ta áp dụng lại lập luận trên. Quy nạp theo số bộ phim, ta có điều phải chứng minh.
¶ Ví dụ: Tasks and Deadlines - CSES
Bạn có công việc cần xử lý. Mỗi công việc có thời lượng và hạn chót . Bạn sẽ xử lý chúng liên tiếp và tuần tự theo thứ tự tuỳ chọn, bắt đầu từ thời điểm . Phần thưởng của một công việc là điểm (có thể âm) với là thời điểm hoàn thành công việc đó.
Nếu hành động tối ưu, phần thưởng tối đa là bao nhiêu?
Lời giải và chứng minh
Quy luật tham lam đúng là làm các công việc theo thời lượng tăng dần và không quan tâm đến hạn chót. Thật vậy, xét 2 công việc liên tiếp có thời lượng lần lượt là và :
Khi này bằng việc đảo thứ tự và , ta sẽ thiệt điểm từ nhưng sẽ được thêm điểm từ nên tổng điểm sẽ tăng thêm , qua đó ta nhận được kết quả tốt hơn. Mọi thứ tự công việc chưa được sắp xếp tăng dần theo thời lượng đều tồn tại ít nhất một cặp công việc kề nhau như vậy, và mỗi lần đổi chỗ như trên thì ta được kết quả tốt hơn. Qua đó ta suy ra được thứ tự sắp xếp tăng dần theo thời lượng cho kết quả tối ưu, tức điều phải chứng minh.
¶ Tìm cận và dựng nghiệm
Một cách khác để áp dụng nguyên lý cực hạn, là tìm cận trên/cận dưới của đáp án theo yêu cầu đề bài, và chỉ ra cách dựng ra một nghiệm thoả mãn cận đó. Khi đó tính tối ưu của nghiệm là hiển nhiên.
¶ Ví dụ: ARC120D - Bracket Score 2
Cho dãy số nguyên có phần tử. Xét một dãy ngoặc đúng bất kì độ dài , với mỗi vị trí có ngoặc mở ta tìm vị trí ngoặc đóng tương ứng với nó và giá trị của tăng thêm một lượng . Dựng dãy ngoặc đúng ứng với dãy có giá trị lớn nhất.
Ví dụ, với dãy số và dãy ngoặc sau:
Ta có giá trị là:
Lời giải và chứng minh
Phần 1: Cận trên
Tổng giá trị của dãy ngoặc là . Ta biết rằng . Do đó, giá trị của dãy ngoặc có thể viết lại thành:
Theo đó, giá trị tối đa không thể vượt quá: (Tổng số lớn nhất) - (Tổng số nhỏ nhất). Ta chứng minh luôn tồn tại dãy ngoặc đạt được giá trị này.
Phần 2: Dựng dãy
Ta cần chỉ ra một cách phân chia dãy phần tử thành tập ( phần tử nhỏ nhất) và tập ( phần tử lớn nhất) và một dãy ngoặc đúng sao cho mỗi cặp ngoặc đều gồm một phần tử thuộc và một phần tử thuộc .
Ta sử dụng cấu trúc dữ liệu stack. Xét phần tử thứ trong mảng:
- Nếu stack rỗng, hoặc phần tử hiện tại cùng tập với đỉnh stack, ta thêm chỉ số vào đỉnh stack, khi này vị trí thứ sẽ là ngoặc mở.
- Nếu stack không rỗng và phần tử thứ khác tập với phần tử ở đỉnh stack có chỉ số , ta ghép được với là cặp ngoặc tương ứng, với là ngoặc mở và là ngoặc đóng.
Phần 3: Chứng minh
Ta chứng minh cách dựng trên cho ra một dãy ngoặc đúng và đạt cận trên.
Trước hết, ở mọi thời điểm stack chỉ chứa các phần tử của cùng một tập, vì ta chỉ đẩy thêm vào khi phần tử mới cùng tập với đỉnh stack. Tiếp theo, khi kết thúc stack phải rỗng. Thật vậy, giả sử còn phần tử, chúng cùng thuộc một tập, gọi là . Ta đã ghép được cặp, mỗi cặp chứa đúng một phần tử của , nên , mâu thuẫn với việc mỗi tập có đúng phần tử.
Thuật toán in ra ngoặc mở mỗi khi đẩy vào stack, ngoặc đóng mỗi khi lấy ra, không bao giờ lấy ra khi stack rỗng, và kết thúc với stack rỗng. Điều này thoả mãn tính chất của dãy ngoặc đúng. Cuối cùng, ta đã ghép đủ cặp, mỗi cặp gồm hai phần tử thuộc hai tập khác nhau, nên giá trị thu được chính là cận trên của bài toán. Ta có điều phải chứng minh.
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// Lưu giá trị và chỉ số ban đầu để sort
vector<pair<int, int>> a(2 * n);
for (int i = 0; i < 2 * n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
// Sắp xếp để phân loại N số nhỏ và N số lớn
sort(a.begin(), a.end());
// type[i] = 0 nếu a[i] thuộc nhóm nhỏ, 1 nếu thuộc nhóm lớn
vector<int> type(2 * n);
for (int i = 0; i < n; ++i)
type[a[i].second] = 0; // N số nhỏ nhất
for (int i = n; i < 2 * n; ++i)
type[a[i].second] = 1; // N số lớn nhất
stack<int> st; // Lưu loại (0 hoặc 1) của ngoặc mở chưa được ghép
string ans = "";
for (int i = 0; i < 2 * n; ++i) {
// Nếu stack không rỗng và phần tử hiện tại khác loại với đỉnh stack
// => Ghép được cặp |nhỏ - lớn| => Đóng ngoặc
if (!st.empty() && st.top() != type[i]) {
ans += ')';
st.pop();
}
// Ngược lại: Cùng loại hoặc stack rỗng => Phải mở ngoặc mới
else {
ans += '(';
st.push(type[i]);
}
}
cout << ans << endl;
return 0;
}
¶ Các kết quả thường dùng
¶ Ví dụ: Bất đẳng thức hoán vị
Cho hai dãy và . Trong mọi cách ghép cặp với ( là một hoán vị), tổng lớn nhất khi ghép cùng chiều ( là hoán vị đồng nhất) và nhỏ nhất khi ghép ngược chiều ( với ).
Chứng minh
Giả sử trong cách ghép có mà ghép với , ghép với với (ghép chéo). Đổi lại cho ghép , ghép , tổng thay đổi một lượng . Vậy mỗi khi ta tháo một cặp chéo thì tổng không giảm, và khi không còn cặp chéo nào thì ta đang ghép hai dãy tăng cùng chiều và có điều phải chứng minh. Ý nhỏ nhất chứng minh tương tự.
¶ Ví dụ: Cực tiểu hoá tổng
Cho một mảng số . Tìm sao cho biểu thức sau đạt giá trị nhỏ nhất:
Ta sẽ tập trung vào hai trường hợp cơ bản và phổ biến nhất, có nhiều ứng dụng trong các bài toán: và .
Trường hợp 1:
Giá trị tối ưu khi này nằm trong khoảng trung vị của mảng . Nói như vậy vì khi chẵn thì mảng sẽ có 2 trung vị, khi này tất cả nằm giữa 2 trung vị này cũng sẽ tối ưu. Nếu lẻ thì là trung vị đúng của mảng.
Chứng minh
Ta viết lại tổng bằng cách gom cặp các phần tử đầu và cuối:
Xét một cặp bất kỳ với . Theo bất đẳng thức giá trị tuyệt đối, ta luôn có:
Dấu "" xảy ra khi và chỉ khi . Do đó để nhỏ nhất toàn cục, phải thỏa mãn dấu bằng xảy ra cho tất cả các cặp
Điều này nghĩa là phải thuộc giao của tất cả các đoạn . Giao của các đoạn lồng nhau này chính là trung vị của mảng (nếu lẻ) hoặc khoảng trung vị của mảng (nếu chẵn). Tổng kết lại, ta có phải nằm trong khoảng trung vị của dãy , tức điều phải chứng minh.
Giá trị của khi thay đổi với mảng gồm số nguyên ngẫu nhiên trong khoảng , hai đường thẳng màu xanh thể hiện hai trung vị của dãy
Trường hợp 2:
Giá trị tối ưu khi này sẽ là trung bình cộng của mảng .
Chứng minh
Thật vậy, ta khai triển thành
Đây là tam thức bậc hai dạng với và có dạng một parabol với bề lõm quay lên trên. Theo kiến thức toán lớp 9, đỉnh của parabol ứng với cực tiểu của đạt tại:
Giá trị của khi thay đổi với mảng gồm số nguyên ngẫu nhiên trong khoảng , đường thẳng màu xanh thể hiện trung bình cộng của dãy
¶ Cấu trúc con tối ưu và tính chất lựa chọn tham lam
Một bài toán có tính chất cấu trúc con tối ưu nếu như nghiệm tối ưu của nó có thể thu được từ nghiệm tối ưu của các bài toán con. Tính chất này là nền của cả quy hoạch động lẫn tham lam. Điều quyết định tính đúng đắn của thuật toán tham lam là tính chất thứ hai, tính chất lựa chọn tham lam: ở mỗi bước, tồn tại một nghiệm tối ưu toàn cục chứa lựa chọn tối ưu cục bộ mà ta đang định thực hiện.
¶ Tham lam vs. quy hoạch động
Tham lam có thể xem như một lớp trường hợp đặc biệt của lớp các bài toán Quy hoạch động. Quy hoạch động chỉ cần tính chất cấu trúc con tối ưu: ở mỗi bước nó giải mọi bài toán con ứng với mọi lựa chọn, rồi mới quyết định. Tham lam ngoài điều kiện đó sử dụng thêm tính chất lựa chọn tham lam để đảo ngược thứ tự ấy: quyết định lựa chọn trước, rồi giải đúng bài toán con ứng với lựa chọn đó. Do đó về lý thuyết, một bài toán có thể giải được bằng tham lam cũng có thể giải được bằng quy hoạch động, nhưng không phải ngược lại.
Tính chất lựa chọn tham lam chính là mấu chốt giúp giảm không gian trạng thái của bài toán xuống đáng kể, nên một lời giải tham lam đúng sẽ có độ phức tạp thấp hơn và nhanh hơn so với lời giải quy hoạch động cho cùng một bài toán.
Ví dụ, bài toán tìm đường đi ngắn nhất trên đồ thị trọng số không âm có thể giải bằng tham lam sử dụng thuật toán Dijkstra với độ phức tạp , cũng như có thể giải bằng quy hoạch động sử dụng thuật toán Bellman-Ford với độ phức tạp . Ta biết rằng thuật toán Dijkstra sẽ luôn chạy nhanh hơn, tuy nhiên nếu đồ thị có trọng số âm thì Dijkstra sẽ không thể giải được mà phải sử dụng Bellman-Ford.
Ta cùng đến với một số ví dụ khác.
¶ Ví dụ: Chia tiền xu
Tìm số đồng xu ít nhất cần để trả được đồng bằng các đồng tiền có mệnh giá .
Lời giải
Với tập như trên, việc tham lam luôn chọn mệnh giá lớn nhất để trả sẽ cho kết quả tối ưu. Chẳng hạn với mệnh giá , chừng nào thì ta sẽ luôn trả bằng 5 đồng, đưa về bài toán con với mệnh giá . Rồi ta làm tương tự với các mệnh giá nhỏ hơn cho đến hết.
Bây giờ đổi tập mệnh giá thành và trả 6 đồng. Tham lam cho , ta cần 3 đồng; còn tối ưu là , chỉ cần hai đồng. Cấu trúc con tối ưu vẫn còn nguyên -- trả tối ưu vẫn bao gồm trả tối ưu với là đồng đầu tiên nào đó, và đó là lý do quy hoạch động vẫn giải được -- nhưng tính chất lựa chọn tham lam đã mất: không có nghiệm tối ưu nào chứa đồng 4.
Tập các mệnh giá mà ta có thể tham lam để trả được ít đồng xu nhất gọi là hệ chuẩn tắc (canonical system), các bạn có thể dễ thấy sự hữu ích và tiện lợi của nó trong hệ thống tiền tệ của các quốc gia hiện tại. Việc kiểm tra một hệ mệnh giá có chuẩn tắc hay không cũng là một bài toán thú vị (các bạn có thể đọc thêm trong Phụ lục), còn với các tập mệnh giá không chuẩn tắc thì ta phải sử dụng Quy hoạch động.
¶ Ví dụ: Cái túi phân số và cái túi 0/1
Có món đồ, món có khối lượng và giá trị , và một cái túi sức chứa . Ở bài toán cái túi phân số, ta được lấy một phần bất kỳ của mỗi món (lấy tỉ lệ của món thì được giá trị và tốn sức chứa); ở bài toán cái túi 0/1, mỗi món chỉ được lấy nguyên hoặc không lấy. Cả hai đều hỏi giá trị lớn nhất bỏ được vào túi.
Lời giải và chứng minh
Với bài toán cái túi phân số, ta có thuật toán sau:
- Sắp xếp các món đồ theo tỉ lệ giá trị trên khối lượng giảm dần
- Với mỗi món, nếu còn đủ chỗ thì ta lấy hết cả món đó, nếu không thì lấy một phần.
Chứng minh: Gọi món là món có tỉ lệ cao nhất. Giả sử một nghiệm tối ưu chưa lấy hết món dù túi đã đầy; khi đó nó có lấy một lượng khối lượng nào đó của một món khác. Bỏ khối lượng của món , thay bằng khối lượng của món , giá trị thay đổi một lượng . Vậy tồn tại nghiệm tối ưu lấy hết món (hoặc lấy đầy túi bằng món nếu ), phần còn lại là bài toán con cùng dạng.
Với cái túi 0/1, lập luận trên sẽ sai ở chỗ "thay khối lượng" vì khi này ta không còn được lấy một phần nữa. Với phản ví dụ sau: , ba món . Tỉ lệ giảm dần là , tham lam lấy hai món đầu được , nhưng lấy hai món sau được . Bài toán khi này có cấu trúc con tối ưu và có thể giải bằng quy hoạch động quen thuộc nhưng không còn tính chất lựa chọn tham lam nữa.
¶ Bài tập: Missing Coin Sum - CSES
Cho 1 tập các đồng xu có mệnh giá . Tìm mệnh giá nhỏ nhất không trả được bằng một tập con phân biệt của các đồng xu trên. Ví dụ với tập các đồng xu thì ta có thể trả được nhưng không có tập con nào trả được , nên đáp án là .
Lời giải
Giả sử . Ta coi và . Đặt . Khi đó ta tìm giá trị đầu tiên sao cho . Khi đó chính là đáp án.
Chứng minh:
Bước cơ sở:
Xét đồng xu đầu tiên . Ta có .
- Nếu : Theo công thức, . Đáp án là 1. Điều này đúng vì nếu đồng xu nhỏ nhất lớn hơn 1, ta không thể tạo ra 1.
- Nếu : Ta tạo được đoạn . Ta tiếp tục xét các đồng xu sau.
Bước quy nạp:
Giả sử với đồng xu đầu tiên, ta đã tạo được mọi giá trị nguyên liên tiếp trong đoạn (bao gồm 0 là tập rỗng). Xét đồng xu tiếp theo là . Khi thêm vào, các giá trị mới ta có thể tạo ra là:
Trong đó ta tạo thêm được đoạn giá trị: . Lúc này, tập hợp tất cả các giá trị có thể tạo được là hợp của hai đoạn:
Ta xét hai trường hợp của :
- . Khi đó, đoạn thứ hai bắt đầu tại , mà . Điều này có nghĩa là đoạn thứ hai sẽ nối tiếp hoặc giao với đoạn thứ nhất. Hợp của chúng sẽ là một đoạn liên tục:
Ta vẫn tạo được mọi giá trị từ đến và quy nạp tiếp tục.
- . Ta có không nằm trong đoạn và nhỏ hơn (theo giả thiết trường hợp này), nên nó cũng không nằm trong đoạn . Suy ra không có cách nào tạo ra được . Theo giả thiết quy nạp, ta đã có cách tạo được hết các giá trị , nên chính là giá trị nhỏ nhất không thể tạo được. Ta có điều phải chứng minh.
¶ Tham lam và tìm kiếm nhị phân
Trong một số bài toán, tham lam không đứng một mình mà đóng vai trò hàm kiểm tra cho tìm kiếm nhị phân. Nếu đáp án có tính đơn điệu -- "làm được với " kéo theo "làm được với mọi " -- thì ta có thể giải bài toán bằng tìm kiếm nhị phân trên , với mỗi cần trả lời nhanh câu hỏi có/không. Câu hỏi có/không này thường dễ hơn hẳn bài toán tìm tối ưu ban đầu, và tham lam là một trong những công cụ tự nhiên để trả lời nó.
¶ Ví dụ: Array Division - CSES
Cho mảng số nguyên dương, chia mảng thành đoạn liên tiếp sao cho tổng lớn nhất trong các đoạn là nhỏ nhất. In ra tổng nhỏ nhất này.
Lời giải và chứng minh
Ta giải bài toán này bằng tìm kiếm nhị phân đáp án. Với cố định, câu hỏi là: có chia được thành không quá đoạn, mỗi đoạn tổng hay không? Ta có thể giải bài toán này bằng tham lam đơn giản: duyệt từ trái sang phải, cứ thêm phần tử vào đoạn hiện tại chừng nào tổng còn , nếu không được nữa thì mở đoạn mới. Nếu số đoạn thì trả lời có. (Chia được thành ít đoạn hơn thì cũng chia được thành đúng đoạn, bằng cách tách nhỏ một đoạn nào đó.)
Vì sao tham lam trả lời đúng? Gọi là các vị trí kết thúc đoạn của tham lam, và là của một cách chia hợp lệ bất kỳ. Ta chứng minh với mọi bằng quy nạp: đoạn thứ của tham lam bắt đầu tại , tức không sớm hơn đoạn thứ của cách chia kia. Vì các phần tử đều dương, đoạn là một phần của đoạn nên có tổng , và tham lam kéo dài tối đa nên kết thúc không sớm hơn . Do đó tham lam dùng số đoạn ít nhất trong mọi cách chia hợp lệ; nếu tham lam cần nhiều hơn đoạn thì không có cách chia mảng thoả mãn.
Độ phức tạp của bài toán là .
¶ Exchange Argument - Lập luận hoán đổi
Ở các bài toán cơ bản chúng ta đã biết về thứ tự tham lam đơn giản. Tuy nhiên có những bài toán mà cấu trúc thứ tự của đáp án tối ưu không dễ để nhìn ra ngay. Khi này, ta sẽ đi từ trường hợp đơn giản khi chỉ có phần tử. Bằng việc hoán đổi 2 phần tử và biến đổi tương đương các đại lượng, ta có thể biện luận được thứ tự phức tạp và tối ưu để xử lý các phần tử. Đây cũng là phương pháp phổ biến để chứng minh tính đúng đắn của thuật toán tham lam.
¶ Từ hoán đổi kề đến thứ tự toàn cục
Trước khi vào ví dụ, ta phát biểu bổ đề mà mọi lập luận hoán đổi đều dựa vào, và cũng đã dùng ở phần trước.
Bổ đề. Giả sử ta có một quan hệ " nên đứng trước " giữa các phần tử, thoả hai điều kiện:
- Nó là một quan hệ thứ tự hợp lệ (chính xác là thứ tự yếu nghiêm ngặt).
- Trong bất kỳ dãy nào, đổi chỗ hai phần tử kề nhau đang đứng sai thứ tự không làm đáp án xấu đi.
Khi đó dãy đã sắp xếp theo quan hệ này là tối ưu.
Chứng minh. Lấy một dãy tối ưu bất kỳ. Nếu nó chưa được sắp xếp, phải tồn tại hai phần tử kề nhau đứng chưa đúng thứ tự (nếu mọi cặp kề đều đúng thứ tự thì theo tính bắc cầu cả dãy đã đúng thứ tự). Ta đổi chỗ cặp đó: theo (2) đáp án không xấu đi, nên dãy mới vẫn tối ưu, và số cặp nghịch thế (tính theo quan hệ) giảm đi đúng một. Lặp lại thao tác trên sau hữu hạn bước ta thu được dãy đã sắp xếp theo quan hệ mà vẫn tối ưu. Ta có điều phải chứng minh.
Để áp dụng Exchange Argument trong các bài toán, ta cần chỉ ra điều kiện để " trước " tốt hơn " trước " khi chúng kề nhau, rồi sau đó phải kiểm tra điều kiện đó có phải một quan hệ thứ tự hợp lệ hay không. Điều kiện thứ hai hay bị bỏ qua, và ví dụ dưới đây sẽ minh hoạ điều này.
¶ Ví dụ: Chia vàng (NOIP Trung Quốc 2012)
Có một ông vua và ông quan. Ông vua muốn chia thưởng cho các ông quan theo quy tắc sau:
- Ông vua viết lên tay trái số nguyên và tay phải mình số nguyên . Với mỗi ông quan, ông quan thứ viết lên tay trái số và tay phải số .
- Sau khi viết xong, ông vua và ông quan xếp thành 1 hàng dọc, ông vua luôn đứng đầu hàng.
- Sau khi xếp hàng, ông quan thứ sẽ được nhận số vàng bằng tích tất cả số bên tay trái của những người đứng trước ông ta (cả ông vua và ông quan) chia cho số ở tay phải ông ta (làm tròn xuống).
Tìm cách để ông vua xếp thứ tự ông quan đứng sau mình sao cho số vàng của ông quan được thưởng nhiều nhất là ít nhất.
Ý tưởng và lời giải
Gọi với đứng trước , khi này ông quan thứ nhận được vàng còn ông quan thứ nhận được vàng.
Nếu ta đảo chỗ hai ông quan và thì khi này ông nhận vàng còn ông nhận được vàng. Những ông quan khác không bị ảnh hưởng, vì tích các số bên tay trái đứng trước họ không đổi.
Thứ tự không tệ hơn thứ tự khi và chỉ khi:
tương đương với (nhân hai vế với ):
Đến đây, việc dùng luôn bất đẳng thức trên làm hàm so sánh khi cài đặt sắp xếp có thể dẫn đến kết quả sai vì đây không phải một quan hệ thứ tự hợp lệ: chẳng hạn với ba ông quan , cặp thứ nhất và thứ hai "bằng nhau" theo bất đẳng thức, cặp thứ hai và thứ ba cũng "bằng nhau", nhưng để tối ưu thì lại phải đứng ngay trước .
Để giải quyết vấn đề này, ta cần tìm một khoá sắp xếp thực sự ứng với mỗi phân tử. Ta chứng minh bổ đề sau: sắp xếp theo tăng dần thì mọi cặp kề nhau đều thoả bất đẳng thức trên. Thật vậy, nếu thì , và (do ). Do đó suy ra (điều phải chứng minh).
Tổng kết lại, thứ tự sắp xếp theo tăng dần là tối ưu. Khi cài đặt, ta chỉ cần sắp xếp theo tích rồi duyệt một lượt để tính đáp án.
Trong thực tế, Exchange Argument còn được sử dụng phổ biến trong các bài toán Quy hoạch động, chủ yếu là để tìm thứ tự trong các bài toán về việc chọn một tập con tối ưu mà thứ tự thêm các phần tử sẽ ảnh hưởng đến đáp án. Ta cùng đến với một bài toán như vậy:
¶ Bài tập: ABC366F - Maximum Composition
Cho hàm tuyến tính . Tính giá trị lớn nhất của hàm hợp với là các bộ số khác nhau.
Giới hạn: .
Lời giải và chứng minh
Phần 1: Exchange Argument
Giả sử ta đã chọn được hàm hợp có hàm số tối ưu. Ta cần xác định thứ tự áp dụng để đạt giá trị lớn nhất. Xét 2 hàm số và được chọn. Giả sử ta áp dụng chúng liền kề nhau lên giá trị hiện tại :
- Áp dụng trước, sau .
- Áp dụng trước, sau .
Để thứ tự trước, sau tốt hơn, ta cần có:
Hàm nào có giá trị lớn hơn sẽ được ưu tiên áp dụng trước. Ta sẽ sắp xếp các hàm số theo biểu thức trên, qua đó tạo thêm được giả thiết cho bài toán (từ các bộ bất kì thành các bộ có chỉ số tăng dần). Khi này ta có thể giải bằng motif Quy hoạch động quen thuộc.
Phần 2: Quy hoạch động
Gọi là giá trị lớn nhất tạo được với hàm hợp của hàm số. Duyệt qua danh sách hàm số đã sắp xếp: Với mỗi hàm , ta xem xét việc áp dụng hàm này sau khi đã áp dụng hàm trước đó. Công thức chuyển trạng thái như sau:
Khởi tạo: (đề bài cho ), các vị trí khác .
Cài đặt
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 2e18;
struct Func {
int a, b;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<Func> funcs(n);
for (int i = 0; i < n; ++i) {
cin >> funcs[i].a >> funcs[i].b;
}
// Sắp xếp theo Exchange Argument
// Hàm nào có độ ưu tiên cao hơn (B/(A-1) lớn hơn) sẽ được xét trước
sort(funcs.begin(), funcs.end(), [](const Func &x, const Func &y) {
// So sánh: x.b / (x.a - 1) > y.b / (y.a - 1)
// Chuyển vế nhân để tránh chia cho 0 và sai số số thực
return (long long)x.b * (y.a - 1) > (long long)y.b * (x.a - 1);
});
// DP: dp[j] = Giá trị lớn nhất của hàm hợp đã có j hàm số
vector<long long> dp(k + 1, -INF);
dp[0] = 1; // Giá trị khởi đầu đề bài cho là 1
// Với mỗi hàm, ta xem xét thêm nó vào hợp của j - 1 hàm đã áp dụng trước đó
for (const auto &f : funcs) {
// Duyệt ngược để đảm bảo mỗi hàm chỉ dùng 1 lần cho mỗi trạng thái
for (int j = k; j >= 1; --j) {
if (dp[j - 1] > -INF) {
// Thử áp dụng hàm f vào kết quả của chuỗi j-1 hàm trước đó
long long next_val = f.a * dp[j - 1] + f.b;
if (next_val > dp[j]) {
dp[j] = next_val;
}
}
}
}
cout << dp[k] << "\n";
return 0;
}
¶ Regrettable Greedy - Sửa lại lựa chọn
Ta đã biết rằng thuật toán tham lam sẽ không bao giờ xét lại các lựa chọn đã đưa ra. Tuy nhiên, ở cấp độ nâng cao hơn, Regrettable Greedy là một dạng thuật toán vẫn mang bản chất tham lam - tại mỗi bước, thuật toán vẫn luôn đưa ra một quyết định tối ưu cục bộ ngay lập tức. Nhưng ngoài ra, nó có một cơ chế cho phép "hối tiếc" (Regret): nếu ở các bước sau, thuật toán nhận ra quyết định tham lam trước đó làm ảnh hưởng đến kết quả toàn cục, nó có một cơ chế đặc biệt cho phép thu hồi một phần quyết định cũ để nhường chỗ cho lựa chọn tốt hơn.
¶ Ví dụ: Time Travel
Cho một mảng các số nguyên dương. Tìm cách gán dấu âm cho nhiều phần tử nhất có thể sao cho vẫn đảm bảo mọi tổng tiền tố của mảng đều dương.
Ý tưởng và lời giải
Khi duyệt qua từng phần tử của mảng, ta ban đầu luôn ưu tiên gán dấu âm cho nó để tăng số lượng phần tử âm, đồng thời đẩy giá trị âm này vào một Priority Queue min (do đó sẽ trả về số âm có giá trị tuyệt đối lớn nhất) và cập nhật tổng tiền tố hiện tại.
Nếu tại bất kỳ bước nào việc đổi dấu vi phạm điều kiện tổng tiền tố dương, ta có thể quay lại, đưa những phần tử ta vừa gán dấu âm trước đó về như cũ. Để tối ưu thì ta sẽ chọn số âm trong Priority Queue đang có giá trị tuyệt đối lớn nhất và đổi lại nó về dương, khi này ta sẽ có nhiều khả năng hơn để gán dấu âm cho các phần tử tiếp theo. Để ý rằng ta chỉ cần đổi đúng một phần tử là đủ: phần tử bị đổi có giá trị tuyệt đối không nhỏ hơn phần tử vừa thêm, nên tổng tiền tố sau khi đổi ít nhất bằng tổng tiền tố ở bước trước, vốn đã dương.
Sau khi duyệt hết mảng, số lượng phần tử còn lại trong Priority Queue chính là số lượng số âm tối đa thỏa mãn đề bài. Độ phức tạp là .
¶ Bài tập: CF865D - Buy Low Sell High
Đây cũng là bài ABC250G - Stonks.
Bạn có thông tin giá cổ phiếu của ngày tiếp theo. Mỗi ngày bạn có thể chọn bán 1 đơn vị cổ phiếu với giá của ngày hôm đó, hoặc mua tích trữ 1 đơn vị cổ phiếu với giá của ngày hôm đó để bán sau, hoặc không làm gì. Lúc bắt đầu bạn không có cổ phiếu và sau ngày phải giao dịch được hết cổ phiếu đang có. Hỏi lợi nhuận tối đa thu được là bao nhiêu?
Ý tưởng và lời giải
Trong bài toán này, chúng ta sẽ "thử" giao dịch nếu thấy có lãi, nhưng sẽ lưu lại thông tin để hoàn tác giao dịch này và sửa sai trong tương lai. Ta dựng một Priority Queue thể hiện danh sách quyền mua. Tại ngày với giá , ta làm như sau:
- Ta luôn coi là một cơ hội mua tiềm năng và thêm vào PQ. Nếu lớn hơn quyền mua thấp nhất hiện có trong quá khứ (), ta thực hiện khớp lệnh mua tại và bán tại để kiếm lời ngay lập tức: . Việc ưu tiên chọn để khớp lệnh là chiến lược tốt nhất vì nó không chỉ tối đa hóa lợi nhuận tức thời mà còn an toàn hơn về điều kiện giao dịch (vì dễ khớp lệnh hơn). Quan trọng nhất, việc "chốt lãi" sớm này không làm mất nghiệm tối ưu toàn cục, bởi bất kỳ lợi ích tiềm năng nào của việc để dành cho tương lai đều có thể được bù đắp bởi cơ chế sửa sai ở bước sau.
- Khi ta quyết định khớp lệnh mua ở với lệnh bán ở , ta vẫn đẩy lại vào PQ. Thao tác này đóng vai trò như một công cụ toán học biến đổi trạng thái từ "vừa bán tại " thành một "quyền mua ảo tại ". Nếu trong tương lai xuất hiện giá bán lời hơn , ta sẽ dùng chính quyền mua ảo này để khớp lệnh (sửa lại lựa chọn). Khi đó, tổng lợi nhuận của chuỗi giao dịch sẽ là tổng đại số: . Tức là việc sửa lại lựa chọn tương đương với việc ta đã đưa ra quyết định lời hơn (bán ở ) ngay từ đầu mà không vi phạm ràng buộc nào của bài toán.
Cài đặt
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// Min-Priority Queue để lưu giá các quyền mua (cũng như để sửa lại lựa chọn)
priority_queue<long long, vector<long long>, greater<long long>> pq;
long long total_profit = 0;
for (int i = 0; i < n; ++i) {
long long current_price;
cin >> current_price;
// Luôn luôn push giá hiện tại vào PQ.
// Ý nghĩa: Ta luôn có quyền mua cổ phiếu này tại ngày hôm nay.
pq.push(current_price);
// Kiểm tra xem có thể bán (hoặc sửa lại lựa chọn) để có lời không
if (pq.top() < current_price) {
// Giá thấp nhất trong quá khứ
long long buy_price = pq.top();
// Cộng lợi nhuận giả định vào tổng
total_profit += current_price - buy_price;
// Xóa giá mua đó đi (vì đã được dùng để khớp với lệnh bán này)
pq.pop();
// Cơ chế sửa lại lựa chọn: Push giá cổ phiếu hiện tại vào lại PQ
// Ý nghĩa: Ta vừa bán ở 'current_price', nhưng ta trao cho tương lai quyền
// "mua lại" chính cổ phiếu này với giá 'current_price' để bán ở mức cao hơn.
// Về toán học: (p_new - p_old) + (p_future - p_new) = p_future - p_old.
pq.push(current_price);
}
}
cout << total_profit << endl;
return 0;
}
Đọc thêm: Liên hệ với bài toán Luồng cực đại
Kĩ thuật sửa lại lựa chọn này có liên hệ với bài toán tìm luồng cực đại (và thậm chí là luồng min-cost). Cách làm ngây thơ (và sai) là lặp lại việc tìm một đường đi bất kì từ nguồn đến đích còn sức chứa, rồi đẩy luồng theo đường đó. Một phản ví dụ có thể kể đến là xét đồ thị bốn đỉnh với các cạnh , , , đều có sức chứa 1 và thêm cạnh sức chứa 1. Nếu đường đầu tiên tìm được là , ta đẩy được 1 đơn vị và sau đó không còn đường nào: đã đầy, đã đầy. Nhưng luồng cực đại là 2 ( và ).
Thuật toán cơ bản và dễ tiếp cận nhất của bài toán luồng cực đại là Ford-Fulkerson sửa điều này bằng cách thêm cạnh ngược: mỗi khi đẩy đơn vị qua cạnh , ta thêm cạnh ngược với sức chứa . Đường tăng luồng đi qua cạnh ngược có nghĩa là "rút lại" một phần luồng đã đẩy trước đó. Trong ví dụ trên, sau bước đầu ta có đường , trong đó là cạnh ngược: nó huỷ quyết định đẩy luồng qua , và kết quả là hai đường , như mong muốn. Toàn bộ mục này là những bài toán mà ta có thể cài đặt một cơ chế "cạnh ngược" như vậy một cách gọn hơn nhiều so với việc dựng đồ thị luồng thật sự.
¶ Kĩ thuật và lưu ý khi cài đặt
Việc tạo ra cấu trúc thứ tự cho dữ liệu trong thuật toán tham lam có 2 cách phổ biến sau:
- Sắp xếp (bằng một hàm so sánh nào đó)
- Sử dụng các cấu trúc dữ liệu duy trì thứ tự sẵn có của C++ STL:
set,multiset,map,priority_queue,...
¶ Sắp xếp
Hàm std::sort trong C++ có cú pháp như sau:
// ví dụ, với vector s
sort(s.begin(), s.end(), func); // sắp xếp theo func
sort(s.rbegin(), s.rend(), func); // sắp xếp theo thứ tự ngược lại của func
với func là hàm so sánh (comparator) tuỳ chọn giữa 2 phần tử bất kì trong mảng. Nếu ta không thiết lập hàm func này, thì kiểu dữ liệu mà ta sử dụng phải có định nghĩa phép toán < của nó. Chẳng hạn, trong bài toán Chia vàng ở phần Exchange Argument, ta có thể cài đặt như sau:
struct Info {
int a, b;
bool operator<(const Info &x) const {
return 1LL * a * b < 1LL * x.a * x.b;
} // so sánh phần tử này với một phần tử khác (gọi là x)
};
¶ Điều kiện hợp lệ của hàm so sánh
Hàm so sánh cmp(x, y) (đọc là " phải đứng trước " hay ) dùng cho std::sort và các cấu trúc STL phải là một thứ tự yếu nghiêm ngặt (strict weak ordering), tức thoả mãn ba điều kiện:
- Không phản xạ:
cmp(x, x)luôn làfalse. Nói riêng, hai phần tử "bằng nhau" thì hàm so sánh phải trả vềfalse. - Bắc cầu:
cmp(x, y)vàcmp(y, z)kéo theocmp(x, z). - Quan hệ "không so sánh được" (cả
cmp(x, y)vàcmp(y, x)đềufalse) cũng phải thoả mãn tính chất bắc cầu: nếu cózsao cho cảcmp(y, z)vàcmp(z, y)đềufalsethì ta cũng phải có cảcmp(x, z)vàcmp(z, x)đềufalse.
Điều kiện thứ ba là điều kiện quan trọng nhất. Hàm so sánh rút thẳng từ bất đẳng thức của bài Chia vàng vi phạm đúng điều kiện này: với , phần tử thứ nhất và thứ hai không so sánh được, thứ hai và thứ ba không so sánh được, nhưng thứ nhất lại nhỏ hơn thứ ba. Vi phạm điều kiện trên, thuật toán có thể gây ra hành vi không xác định (undefined behavior) trong C++: std::sort có thể cho thứ tự sai, và trong một số cài đặt thậm chí truy cập ngoài mảng, do đó có thể gây ra lỗi rất khó debug. Cách phòng tránh tốt nhất là đưa hàm so sánh về dạng so sánh một khoá như đã bàn ở mục Exchange Argument.
Qua kiểm nghiệm của tác giả, khi thử trên các bộ dữ liệu nhỏ được sinh ngẫu nhiên và so với vét cạn, hàm so sánh cho đáp án sai ở khoảng 0.2% số test -- đủ hiếm để qua mặt các test ví dụ sơ sài, cũng như đủ nhiều để không qua được bộ test chính thức (vốn sẽ được sinh rất mạnh và có nhiều trường hợp hiểm). Do đó cài đặt hàm so sánh không hợp lệ có thể gây ra những hậu quả khó lường trong các kì thi (nhất là khi bạn thi những kì thi mà phải đúng hết test trong 1 bài/subtask thì mới qua được bài/subtask đó).
¶ Sử dụng STL
Đối với ngôn ngữ C++, ta có thể thiết lập hàm so sánh cho các cấu trúc dữ liệu STL: set, priority_queue, map,... bằng functor-comparator (đối tượng hàm so sánh). Có hai loại chính:
less<T>: ứng vớioperator <, mặc định các cấu trúc dữ liệu STL sẽ dùng functor này.greater<T>: ứng vớioperator >
Chẳng hạn, priority_queue bình thường sẽ luôn trả về phần tử lớn nhất, bạn có thể khai báo priority_queue<int, vector<int>, greater<int>> để lấy phần tử nhỏ nhất.
Khi khai báo 1 struct, việc định nghĩa phép toán thứ tự < hoặc > trong struct sẽ giúp ta có thể sử dụng chúng ngay lập tức trong các cấu trúc dữ liệu STL.
Đối với C++11 trở đi, ngoài cách khai báo functor như ở trên, ta có thể khai báo dưới dạng lambda rất gọn và nhúng vào bằng từ khoá decltype (declared type). Lưu ý với các chuẩn C++ trước C++20 (từ C++11 đến C++17), ta phải truyền lambda vào constructor khi khai báo cấu trúc dữ liệu do ở các chuẩn đó lambda không có constructor mặc định:
// Trước C++20:
auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s(cmp);
std::priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
// Sau C++20:
auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s;
std::priority_queue<int, vector<int>, decltype(cmp)> pq;
¶ Tham lam trong thực chiến
Trong phần này, chúng ta sẽ cùng đào sâu vào 2 bài toán tham lam hay đã xuất hiện trong kì thi ICPC Regional 2024 tại Hà Nội.
¶ Bài tập: ICPC 2024 Regional Hanoi bài L: Locomotive Lane Logistics
Cho một đường ray có độ dài và truy vấn. Mỗi truy vấn có 1 trong 2 dạng:
+ l v: thêm 1 tàu có độ dài và vận tốc vào lịch trình.- l v: xoá 1 tàu có độ dài và vận tốc khỏi lịch trình, đảm bảo trong lịch trình hiện tại có ít nhất 1 tàu như vậy.
Mỗi con tàu có phần mui và phần đuôi, khoảng cách giữa mui và đuôi của tàu chính là độ dài của nó. Con tàu sẽ xuất phát với mui chạm vạch xuất phát, đi đều liên tục với vận tốc về phía vạch kết thúc và chỉ ra khỏi đường ray khi đuôi rời khỏi vạch kết thúc. Mỗi con tàu ta có thể chọn cho nó thời điểm xuất phát là số thực bất kì.
Sau mỗi truy vấn, tính tổng thời gian ít nhất để đưa toàn bộ tàu trong danh sách ra khỏi đường ray mà không xảy ra tai nạn. Tai nạn có thể xảy ra giữa 2 tàu ở thời điểm mui của tàu đi sau đâm vào đuôi của tàu đi trước, vận tốc của tàu đi sau lớn hơn tàu đi trước và tàu đi trước chưa ra khỏi đường ray. In ra đáp án tối ưu (luôn có dạng là số hữu tỉ) theo modulo .
Giới hạn: .
Lời giải
Trước tiên ta có thể rút ra 2 nhận xét tham lam đầu tiên về đáp án tối ưu:
- Nếu 2 tàu có cùng vận tốc, thì chúng có thể đi nối đuôi nhau như là 1 tàu (vẫn thoả mãn điều kiện không xảy ra tai nạn), nên ta có thể giả sử vận tốc của tất cả các tàu đều khác nhau.
- Để tối thiểu hoá tổng thời gian, các tàu cần di chuyển nối tiếp nhau khít nhất có thể, tàu chậm sẽ đi trước, rồi sau một khoảng thời gian tối ưu ta sẽ cho tàu nhanh hơn xuất phát và đuổi theo sau. Một cách để chứng minh nhận xét này, là tàu đi sau đã tận dụng triệt để khoảng thời gian tàu đi trước chiếm dụng đường ray để tranh thủ di chuyển được một khoảng cách nhất định.
Tiếp theo đó, bằng việc ngồi nháp toán và chứng minh công thức ta rút ra nhận xét quan trọng nhất của bài toán:
- Giả sử có 2 tàu và với . Ta cho đi trước, đi sau và sẽ có xu hướng đuổi kịp. Để tối ưu thời gian, ta căn chỉnh sao cho ngay thời điểm đuôi rời khỏi đường ray thì mui của cũng vừa chạm vạch kết thúc. Theo đó ta có giãn cách thời gian tối ưu giữa 2 tàu:
- Áp dụng nhận xét trên cho tàu, thì tổng thời gian tối ưu là:
Chứng minh: Gọi là tàu chậm nhất. Với các tàu xuất phát trước , ta có đuôi của mỗi tàu phải rời vạch xuất phát trước khi mui tàu kế tiếp chạm vạch (nếu không hai tàu chồng lên nhau ngay tại vạch), nên tàu chiếm vạch xuất phát ít nhất , và xuất phát không sớm hơn tổng các đó. Bản thân cần thêm để ra khỏi đường ray. Cộng lại, tổng thời gian với mọi cách sắp xếp. Các tàu xuất phát sau đều nhanh hơn hoặc bằng nó, mui của chúng luôn nằm sau đuôi , nên chúng chỉ băng qua vạch kết thúc sau khi đã ra hẳn; tại vạch kết thúc mỗi lúc chỉ có một tàu băng qua và tàu chiếm vạch đúng . Vậy nên ta thu được một cách dựng đạt được cận dưới của đáp án, nên công thức của nhận xét là tối ưu.
Để ý rằng chặn dưới không phụ thuộc thứ tự của các tàu khác ngoài , nên qua chứng minh ở trên ta thấy rằng thật ra cho tàu nhanh đi trước cũng có thể đạt được đúng giá trị này. Nhận xét "tàu chậm đi trước" chỉ là một cách dựng, không phải điều bắt buộc.
Tổng kết lại, thuật toán cuối cùng của bài chỉ cần duy trì 2 giá trị sau qua các thao tác thêm và xoá tàu khỏi danh sách:
- Vận tốc của tàu chậm nhất trong danh sách hiện tại, có thể dùng
multisethoặcpriority queue. - Tổng của các tàu đang có trong danh sách hiện tại.
Độ phức tạp cho mỗi truy vấn là .
¶ Bài tập: ICPC 2024 Regional Hanoi bài K: Kangokutou Exodus
Cho một mê cung gồm hành lang vuông góc liên tiếp nhau, mỗi hành lang có độ dài . Bạn đứng ở điểm bắt đầu của hành lang .
Trước khi vượt mê cung. bạn có thể chọn trước độ dài tốc biến nguyên để di chuyển từ điểm bắt đầu của hành lang đến điểm kết thúc của hành lang .
Ở mỗi thời điểm nguyên bạn sẽ tốc biến đúng đơn vị độ dài về phía trước trong giây, nếu cú tốc biến này không chuẩn (khoảng cách từ điểm bạn tốc biến đến điểm cuối của hành lang hiện tại nhỏ hơn đơn vị) thì bạn sẽ tốc biến đến điểm cuối của hành lang và bị choáng giây, điều này áp dụng cả với hành lang cuối. Ngược lại, bạn có thể tốc biến tiếp ngay lập tức mà không bị choáng.
Tính thời gian ngắn nhất có thể để ra khỏi mê cung khi chọn tối ưu.
Giới hạn: .
Lời giải
Vì quá trình di chuyển qua các hành lang là độc lập với nhau, ta có thể sắp xếp lại các hành lang theo thứ tự: .
Chúng ta bắt đầu với một số nhận xét tham lam như sau về đáp án tối ưu:
- Với cho trước thì ta có công thức tổng thời gian hoàn thành:
là kí hiệu Iverson của biểu thức boolean , với nếu đúng và nếu sai.
- Ta nhận thấy rằng đáp án tối ưu có cận dưới và cận trên hiển nhiên là và . Cận dưới xảy ra khi toàn bộ bằng nhau, khi đó ta chọn , còn cận trên xảy ra khi ta cho .
- Luôn tồn tại tối ưu là một trong các , nên ta chỉ cần xét . Thật vậy, giả sử giá trị tối ưu là không trùng với bất cứ nào. Khi này với các thì ta sẽ mất đúng giây để đi qua, còn với thì ta sẽ mất ít nhất giây để đi qua. Do đó , mâu thuẫn với việc tối ưu. Ta có điều phải chứng minh.
Nhận xét thứ 3 gợi ý rằng chúng ta cần duyệt qua tất cả các khác nhau và tính nhanh được . Chúng ta chia mảng thành 3 phần:
- Phần mà , mỗi mất giây.
- Phần , mỗi mất giây.
- Phần còn lại với mỗi mất giây.
Mấu chốt của bài toán là tính phần 3 đủ nhanh khi 2 phần trước ta có thể tính trong . Và thật ra, cách đủ nhanh lại là một ý tưởng tham lam và đặt cận đơn giản:
#include <bits/stdc++.h>
using namespace std;
// Hàm tính thời gian đi qua hành lang độ dài len với bước nhảy m
// Công thức: ceil(len/m) + (1 nếu len không chia hết cho m)
int calculate_cost(int len, int m) {
if (len % m == 0) {
return len / m;
} else {
return (len / m) + 2; // 1 bước cuối + 1 giây choáng
}
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// Sắp xếp để gom nhóm các hành lang có cùng độ dài
// và dễ dàng xử lý các phần tử nhỏ hơn/lớn hơn.
sort(a.begin(), a.end());
// Khởi tạo kết quả ban đầu: trường hợp tệ nhất mỗi hành lang tốn 2s
// (ví dụ chọn m > max(a_i), tất cả đều nhảy quá đà và bị choáng)
long long min_total_time = 2LL * n;
for (int i = 0; i < n;) {
int m = a[i]; // Chọn độ dài bước nhảy m bằng độ dài hành lang hiện tại
// Tìm vị trí cuối cùng có giá trị bằng a[i]
// Đoạn [i, j] là các hành lang có độ dài bằng m (tốn 1s)
int j = i;
while (j < n && a[j] == m) {
j++;
}
// j lúc này là chỉ số của phần tử đầu tiên > m (hoặc n)
// Tính chi phí cơ sở cho lần chọn m này:
// 1. Các hành lang < m: tốn 2s (nhảy quá đà ngay bước 1)
// 2. Các hành lang = m (từ i đến j-1): tốn 1s
// 3. Các hành lang > m (từ j đến n-1): giả sử tạm tính tối thiểu là 2s
// (Thực tế sẽ >= 2s. Ta sẽ cộng phần chênh lệch sau)
long long current_time = i * 2 + (j - i) * 1 + (n - j) * 2;
// Tối ưu: Duyệt các phần tử lớn hơn m từ lớn về bé.
// Cộng thêm chi phí thực tế chênh lệch so với giả định (2s).
// Nếu tổng vượt quá kết quả tốt nhất hiện có thì dừng ngay.
for (int k = n - 1; k >= j; --k) {
int actual_cost = calculate_cost(a[k], m);
current_time += (actual_cost - 2);
if (current_time >= min_total_time) {
break;
}
}
min_total_time = min(min_total_time, current_time);
// Chuyển sang nhóm độ dài tiếp theo
i = j;
}
cout << min_total_time << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin >> tc;
while (tc--)
solve();
return 0;
}
Ý tưởng tóm gọn như sau: Ở một thời điểm bất kì, giá trị của min_total_time là ngưỡng quyết định xem l[i] hiện tại có tối ưu hơn không. Để có thể quyết định nhanh, ta duyệt qua các giá trị từ lớn đến nhỏ, nếu đến một lúc nào đó current_time lớn hơn ngưỡng tối ưu hiện tại thì ta có thể loại luôn l[i].
Độ phức tạp của 2 vòng lặp khi này không phải mà là . Thật vậy, xét một độ dài phân biệt với tần suất :
current_timekhởi đầu bằng (mọi hành lang được tạm tính giây).min_total_timeluôn sau lần xét đầu tiên (nhận xét 2).- Mỗi hành lang có độ dài và tốn ít nhất giây: nếu thì và không chia hết, nếu thì . Mỗi hành lang như vậy cộng thêm ít nhất vào
current_time. Hành lang tốn đúng giây, cộng thêm .
Do đó sau khi duyệt qua không quá hành lang loại thứ nhất, current_time đã đạt min_total_time và vòng lặp trong dừng; xen giữa có thể có thêm không quá hành lang loại thứ hai. Vậy với mỗi phân biệt, vòng lặp trong chạy không quá lần, và tổng đại lượng này trên mọi phân biệt là . Độ phức tạp cuối cùng của bài là do sắp xếp.
¶ Lời kết
Tham lam không chỉ là một dạng bài. Nó là một tư tưởng luôn len lỏi trong giải thuật, và có thể xuất hiện bất cứ đâu trong các bài toán, trong một bước, nhiều bước giải hoặc toàn bộ bài toán. Đây thường là phần hay, độc đáo trong các kì thi, thử thách sự nhanh nhạy, kinh nghiệm và sáng tạo của thí sinh, cũng như trí tuệ của người ra đề. Hi vọng bài viết này đã phần nào đó truyền tải được cái hay của tư tưởng tham lam, để các bạn hào hứng chinh phục những bài toán hay hơn và khó hơn trong tương lai.
¶ Bài tập vận dụng
¶ Tham lam cơ bản
- ICPC SEERC 2023 bài J - Jackpot
- CF1896C - Matching Arrays
- CF1779C - Least Prefix Sum
- ICPC 2025 vòng Quốc gia bài F - Feast of Delicacy
¶ Exchange Argument
- CF632C - The Smallest String Concatenation
- ICPC 2025 vòng Quốc gia bài B - Blowing Balloons
- CF1043E - Train Hard, Win Easy
- AtCoder - Manga Market
- AtCoder - Zabuton
- Singapore NOI 2022 - Gym Badges
¶ Regrettable Greedy
- CF1526C2 - Potion
- CF1974G - Money Buys Less Happiness Now
- CF730I - Olympiad in Programming and Sports
- CF3D - Least Cost Bracket Sequence
¶ Bài khó
- CF436E - Cardboard Boxes
- AGC072A - Rhythm Game
- IOI 2020 ngày 1 bài 3 - Carnival Tickets
- CF1793E - Velepin and Marketing
- NOI 2019 - Sequence
- ICPC World Finals 2018 bài C - Conquer the World
¶ Tài liệu tham khảo / đọc thêm
- CP Handbook by Antti Laaksonen - Greedy algorithms
- How to prove your solution in CP
- USACO Guide | Greedy with Sorting
- Principle of Algorithmic Problem Solving - Greedy
- Chuyên đề tham lam nâng cao - HKOI 2023
- Lecture 3 - Exchange Argument by Errichto
- Algorithms Live! - Exchange Argument
- Kozen, Zaks - Hệ mệnh giá chuẩn tắc