¶ Hàng đợi hai đầu (deque) và Bài toán tìm max-min trong đoạn tịnh tiến
Tác giả:
- Bùi Minh Hoạt - Hung Vuong High School for the Gifted, Phu Tho Province
- Nguyễn Châu Khanh - Hung Vuong High School for the Gifted, Phu Tho Province
Reviewer: Phạm Tuấn Nghĩa
¶ Định nghĩa
Deque (Double-ended queue) là một kiểu dữ liệu trừu tượng tổng quát hóa một hàng đợi. Nó là nó kiểu danh sách mà có thể bổ sung và loại bỏ một phần ở đầu hoặc cuối danh sách.
Các thao tác deque hỗ trợ:
- push_front(): Đẩy vào đầu deque
- push_back(): Đẩy vào cuối deque
- pop_front(): Loại bỏ phần tử ở đầu deque
- pop_back(): Loại bỏ phần tử ở cuối deque
- empty(): Kiểm tra Deque có rỗng không?
- size(): Trả về số phần tử đang có trong deque
Độ phức tạp:
- Độ phức tạp thời gian của tất cả các hoạt động trong deque là
- Độ phức tạp thời gian của truy cập ngẫu nhiên theo chỉ mục là
¶ Bài toán 1
Cho một dãy gồm phần tử được đánh số từ 1 đến . Phần tử thứ có giá trị là . Cho là một số nguyên dương (). Với mỗi phần tử (), tìm giá trị nhỏ nhất của các phần tử trong đoạn từ đến trên dãy .
giá trị nhỏ nhất trong đoạn
Input:
- : chứa hai số nguyên dương cách nhau bởi dấu cách
- : chứa số nguyên dương cách nhau bởi dấu cách
Output: In ra dòng:
- Dòng thứ in ra giá trị nhỏ nhất của các phần tử trong đoạn từ đến .
Ví dụ:
Input
8 4
1 3 5 7 4 5 9 5
Output
1
3
4
4
4
¶ Phân tích
Với bài toán này ta có thể duyệt tất cả các đoạn gồm phần tử liên tiếp trong mảng để tìm giá trị nhỏ nhất.
const int MAXN = 1e5 + 105;
const int INF = 1e9 + 7;
for (int i = K; i <= N; ++i) {
int minRange = +INF;
for (int j = i; j >= i - K + 1; --j)
minRange = min(minRange, A[j]);
cout << minRange << '\n';
}
Tuy nhiên cách làm này không đem lại hiệu quả cao. Độ phức tạp:
Mỗi lần gán thì mấu chốt là những vị trí mà thay đổi. Vậy nên ta sẽ chỉ lưu lại những vị trí có thể làm thay đổi . Ta thấy rằng các vị trí lưu vào tăng dần về cả giá trị cũng như vị trí.
Minh họa
Các ô được tô màu đỏ là các ô làm thay đổi giá trị . Ô thứ có giá trị ta không cần quan tâm vì ngay từ nó đã không nằm trong danh sách các ô màu đỏ.
Tương tự, đối với đoạn ta cũng không cần quan tâm đến ô thứ có giá trị .
Do đó ta có thể làm như sau:
Tìm giá trị nhỏ nhất
Minh họa test: Cho , , dãy
Đầu tiên chúng ta khởi tạo một hàng đợi hai đầu nhằm mục đích lưu vị trí của phần tử có giá trị nhỏ nhất.
Lúc đầu hàng đợi hai đầu của chúng ta rỗng
Đối với phần tử đầu tiên vì do hàng đợi rỗng nên ta sẽ đẩy phần tử này vào cuối hàng đợi
Tiếp theo ta sẽ đẩy lần lượt các phần tử có vị trí và vào cuối hàng đợi.
Vì ta chỉ xét các đoạn trong khoảng từ . Do đó khi ta xét đến phần tử thứ thì phần tử đầu tiên trong hàng đợi có vị trí không còn ý nghĩa gì nữa. Vì vậy ta sẽ loại bỏ phần tử đầu tiên ra khỏi hàng đợi.
Khi ta loại bỏ phần tử đầu tiên ra khỏi hàng đợi thì tất cả các phần tử đứng sau phần tử đó để được đẩy lên ô và hàng đợi sẽ được đánh số lại.
Tiếp đến khi ta chuẩn bị đẩy phần tử thứ vào hàng đợi thì nhận thấy rằng giá trị của nó nhỏ hơn giá trị của phần tử cuối trong hàng đợi.
Liệu rằng phần tử cuối cùng trong hàng đợi kia còn ý nghĩa gì trong việc tính giá trị nhỏ nhất nữa không?
Câu trả lời là . Vì nó đã không phải là giá trị nhỏ nhất trong đoạn rồi thì càng không thể là giá trị nhỏ nhất trong đoạn .
Vì vậy ta sẽ loại bỏ tất cả các phần tử cuối cùng trong deque nếu nó có giá trị lớn hơn hoặc bằng giá trị đang xét.
Sau khi loại bỏ tất cả các phần tử cuối cùng và đẩy phần tử vào thì hàng đợi sẽ có những giá trị sau:
Ta tiếp tục đẩy phần tử thứ vào deque
Sau đó ta tiếp tục đẩy phần tử thứ vào deque
Khi ta chuẩn bị đẩy phần tử thứ vào deque, ta nhận thấy rằng giá trị của nó nhỏ hơn giá trị của phần tử cuối trong hàng đợi. Do đó ta sẽ loại bỏ phần tử cuối cùng trong deque cho đến khi giá trị của phần tử cuối cùng nhỏ hơn giá trị ta chuẩn bị đẩy vào.
Ta có thể rút ra được các nhận xét quan trọng như sau:
- Ở mọi thời điểm, giá trị trong deque luôn tăng nghiêm ngặt. Khi ta đẩy phần tử thứ vào deque thì nó luôn là phần tử có giá trị lớn nhất.
- Vì đây là dãy tăng nghiêm ngặt thế nên phần tử đầu tiên luôn là phần tử nhỏ nhất. (Đây chính là min trong đoạn )
- Tại mỗi bước tính ta chỉ loại bỏ tối đa phần tử đầu deque khi nó không thuộc khoảng đang xét.
- Mỗi phần tử chỉ được đẩy vào deque tối đa lần duy nhất.
Từ các nhận xét như kia, ta có thể dễ dàng hình thành thuật toán. Ta duyệt qua từng phần tử:
- Bước 1: Trong khi hàng đợi khác rỗng và giá trị của phần tử cuối cùng trong deque lớn hơn hoặc bằng giá trị đang xét hiện tại thì ta sẽ đẩy hết ra khỏi hàng đợi.
- Bước 2: Đẩy vị trí của phần tử đang xét hiện tại vào cuối deque. (Ta không nên đẩy giá trị vào bên trong hàng đợi. Vì làm như thế thì ta sẽ rất khó trong việc quản lý đoạn cần lấy kết quả)
- Bước 3: Nếu vị trị của phần tử đầu tiên trong hàng đợi không nằm trong khoảng đoạn xét thì ta loại bỏ nó.
- Bước 4: Đáp án cần tìm chính là giá trị của phần tử đầu tiên trong deque.
¶ Cài đặt
Tìm min trong đoạn tịnh tiến
Ta cần phải sử dụng những cấu trúc sau:
- Cấu trúc dữ liệu hàng đợi hai đầu: - Lưu lại vị trí của phần tử có giá trị nhỏ nhất
- Mảng , lưu các phần tử nhập vào, tốn bộ nhớ
- Mảng , lưu đáp án của bài toán, tốn bộ nhớ
- Để dễ cài đặt thì ta chỉ cần đẩy vị trí vào hàng đợi. Khi ta có vị trị thì ta hoàn toàn có giá trị tương ứng.
deque <int> dq;
/* Làm rỗng deque */
while (dq.size()) dq.pop_front();
/* Duyệt lần lượt các phần tử từ 1 đến N */
for (int i = 1; i <= N; ++i) {
/* Loại bỏ các phần tử có giá trị lớn hơn hoặc bằng A[i] */
while (dq.size() && A[dq.back()] >= A[i]) dq.pop_back();
/* Đẩy phần tử i vào queue */
dq.push_back(i);
/* Nếu phần tử đầu tiên trong deque nằm ngoài khoảng tính
thì ta sẽ loại bỏ ra khỏi deque */
if (dq.front() + k <= i) dq.pop_front();
/* minRange[i] là giá trị nhỏ nhất trong đoạn [i – k + 1 … i] */
if (i >= k) minRange[i] = A[dq.front()];
}
¶ Đánh giá
Tất cả các thao tác cơ bản trên deque (pop_back(), pop_front() và push_back()) có thể dễ dàng được thực hiện với thời gian chạy là .
Mỗi phần tử vào deque đúng lần và bị loại bỏ đúng lần nên độ phức tạp của thuật toán này khi xây dựng là trong mỗi lần tìm trong đoạn tịnh tiến.
¶ Mở rộng
¶ Tìm giá trị lớn nhất
Để tìm giá trị lớn nhất thì ta làm ngược lại quá trình tìm giá trị nhỏ nhất.
Ta sẽ tạo deque nhằm mục đích lưu vị trí của phần tử có giá trị lớn nhất.
Ở bước 1, thay vì loại bỏ các phần tử có giá trị lớn hơn hoặc bằng ra khỏi đầu deque thì ta sẽ loại bỏ các phần tử có giá trị nhỏ hơn hoặc bằng ra khỏi đầu deque. Lúc này, phần tử đầu deque luôn là phần tử lớn nhất. Và ở mọi thời điểm giá trị trong deque luôn là giảm nghiêm ngặt.
¶ Tại sao ta không nên sử dụng cấu trúc dữ liệu cây phân đoạn?
Ta chỉ có thể giải quyết bài toán này bằng cấu trúc dữ liệu .
Để xây dựng được cây thì chúng ta sẽ phải chuẩn bị:
- Bộ nhớ:
- Khởi tạo:
- Ta phải trả lời vị trí. Do đó tổng độ phức tạp sẽ là
¶ Khi nào thì không thể dùng deque để tìm max min trong đoạn tịnh tiến?
Với phương pháp dùng deque để tìm trong đoạn tịnh tiến thì bạn sẽ không thể giải quyết được bài toán sau:
Cho một dãy số có phần tử. Cho truy vấn có dạng:
- : Thay đổi giá trị phần tử thứ thành
- : Tính giá trị nhỏ nhất trong đoạn
- : Tính giá trị lớn nhất trong đoạn
Như đã trình bày ở trên thì độ phức tạp khi xây dựng kĩ thuật tìm trong đoạn tịnh tiến là
Tuy nhiên thuật toán này chỉ thực sự hiệu quả khi chúng ta không có thao tác cập nhật lại giá trị của mảng. Nói cách khác thì với phương pháp này chúng ta chỉ có thể áp dụng khi bài toán là bài toán xử lý offine. Lý do là bởi giả sử chúng ta có M thao tác cập nhật giá trị mà mỗi khi cập nhật lại giá trị thì ta sẽ phải tính lại max và min trong từng vị trí . Lúc này thì độ phức tạp của thuật toán sẽ là và sẽ bị quá thời gian cho phép.
Để giải quyết được bài toán này thì chúng ta có thể sử dụng cấu trúc cây phân đoạn với độ phức tạp là .
¶ Một số lỗi thường gặp
Khi lấy giá trị trong deque ra thì bạn chưa kiểm tra hàng đợi của mình có đang rỗng không? Nếu hàng đợi rỗng mà bạn vẫn lấy giá trị hoặc thì chương trình sẽ sinh lỗi.
¶ Bài toán 2
¶ Đề bài
Trong một round đấu, rồng thần của Hoạt có thể khạc tối đa đạt phát chí mạng vào team địch. Sát thương chí mạng của lần khạc thứ gây ra là . Tuy nhiên rồng thần cần có một khoảng thời gian để hồi lại mana. Vậy nên rồng thần không thể khạc lần chí mạng liên tiếp.
Bạn hãy chỉ cho Hoạt cách điều khiển sức mạnh của rồng thần sao cho tổng sát thương chí mạng gây ra của rồng thần là lớn nhất.
Input:
- Dòng thứ nhất: chứa hai số nguyên
- Dòng thứ hai chứa N số nguyên – sát thương chí mạng lần khạc thứ của rồng thần.
Output: Tổng sát thương chí mạng lớn nhất mà rồng thần có thể gây ra.
Input:
7 3
1 4 2 3 6 5 9
Output:
23
Giải thích: Rồng thần sẽ khạc ở những thời điểm , rồi , sau cùng là . Tổng sát thương sẽ là .
¶ Phân tích
Phân loại bài: data structures, dp
Gọi là tổng sát thương nhỏ nhất mà rồng thần đã bỏ qua khi xét đến vị trí và sẽ tiếp tục bỏ qua phát khạc thứ
Khởi tạo:
- với
Công thức quy hoạch động:
Với thì
Kết quả của bài toán là: Tổng sát thương của phát khạc trừ đi
dp[0] = 0;
for (int i = 1; i <= N + 1; ++i) dp[i] = +INF;
ans = 0;
for (int i = 1; i <= N; ++i) ans += A[i];
for (int i = 1; i <= N + 1; ++i)
for (int j = max(0, i - K); j <= i - 1; ++j)
dp[i] = min(dp[i], dp[j] + A[i]);
cout << ans - dp[N + 1] << '\n';
Độ phức tạp:
Nhận xét:
Ta cập nhật giá trị bởi đoạn các giá trị liên tục. Do đó ta có thể dễ dàng cài đặt bằng cây phân đoạn với độ phức tạp:
Tuy nhiên ta nhận thấy rằng, đây chính là bài toán tìm min trong đoạn tịnh tiến. Ta sẽ làm tương tự như bài toán với độ phức tạp:
¶ Cài đặt
Ta cần phải sử dụng những cấu trúc sau:
- Cấu trúc dữ liệu hàng đợi hai đầu: - Lưu lại vị trí của phần tử có giá trị nhỏ nhất
- Mảng , lưu các phần tử nhập vào, tốn bộ nhớ
- Mảng , lưu đáp án của bài toán, tốn bộ nhớ
- Để dễ cài đặt thì ta chỉ cần đẩy vị trí vào hàng đợi. Khi ta có vị trị thì ta hoàn toàn có giá trị tương ứng.
int ans = 0;
dq.push_back(0);
for (int i = 1; i <= N + 1; ++i) {
while (dq.size() && dq.front() < i - K) dq.pop_front();
dp[i] = dp[dq.front()] + A[i];
ans += A[i];
while (dq.size() && dp[dq.back()] >= dp[i]) dq.pop_back();
dq.push_back(i);
}
cout << ans - dp[N + 1] << '\n';
¶ Bài toán 3
¶ Đề bài
Tòa nhà chọc trời
Có tòa nhà chọc trời được đánh số từ đến . Tòa nhà thứ có độ cao là . Từ tòa nhà thứ ta có thể nhảy đến tòa nhà thứ nếu như thỏa mãn một trong các điều kiện sau:
Hiện tại Gnar đang đứng trên tòa nhà . Mục tiêu của anh ấy là nhảy đến tòa nhà thứ với số lần nhảy là ít nhất. Hãy giúp Gnar nhé!!!
Đầu vào:
- Dòng đầu tiên chứa một số nguyên duy nhất – tổng số lượng nhà chọc trời.
- Dòng thứ hai chứa N số nguyên – chiều cao của các tòa nhà chọc trời.
Đầu ra: In ra số lượng bước nhảy tối thiểu để Gnar có thể nhảy đến tòa nhà thứ .
Ví dụ:
Input
5
1 3 1 4 5
Output
3
Input
4
4 2 2 4
Output
1
Input
5
100 1 100 1 100
Output
2
Bạn có thể nộp bài tại đây
¶ Phân tích
Phân loại bài: data structures, dp, graph
Trường hợp 1: Nếu thì ta có thể xây dựng đồ thị cạnh nối giữa và .
Trường hợp 2: Nếu tòa nhà thứ và thỏa mãn điều kiện nghĩa là tất cả các tòa nhà nằm giữa và đều có chiều cao nhỏ hơn .
Điều này có nghĩa là tồn tại tòa nhà có độ cao lớn nhất trong các tòa nhà từ đến . Nếu thì tất cả các tòa nhà từ đến đều nhỏ hơn .
Làm thế nào để tìm được hai biên nhận tòa nhà k làm max?
Vì nên . Điều này có nghĩa là cả tòa nhà và đều lớn hơn tòa nhà do đó tòa nhà và sẽ không nằm trong khoảng nhận tòa nhà là .
Gọi là vị trí xa nhất tính từ vị trí về bên trái nhận độ cao là
Gọi là vị trí xa nhất tính từ vị trí về bên phải nhận độ cao là
Do đó tòa nhà sẽ là và tòa nhà sẽ là .
Vì nên nếu thì từ tòa nhà ta hoàn toàn có thể nhảy đến tòa nhà . Do đó ta xây dựng đồ thị có cạnh nối giữa tòa nhà với tòa nhà .
Tại sao khi tìm tòa nhà , ta không tìm tòa nhà gần nhất mà lại phải là xa nhất?
Giả sử tòa nhà gần nhất bên trái, bên phải nhận tòa nhà làm lần lượt là và . Khi ta tìm được 2 tòa nhà này thì ta cũng chẳng thể kết luận tòa nhà có thể nhảy sang tòa nhà . Mà giả sử thì , cũng là tòa nhà xa nhất nhận tòa nhà làm .
Vì vậy ta sẽ xét tất cả các tòa nhà để có thể tìm được tòa nhà và thỏa mãn yêu cầu đề bài.
Trường hợp 3: Nếu tòa nhà thứ và thỏa mãn điều kiện nghĩa là tất cả các tòa nhà nằm giữa và đều có độ cao lớn hơn hẳn .
Lập luận tương tự. Ở trường hợp này ta sẽ xây dựng mảng và .
Gọi là vị trí xa nhất tính từ vị trí về bên trái nhận độ cao là
Gọi là vị trí xa nhất tính từ vị trí về bên phải nhận độ cao là
Đối với mỗi vị trí , sẽ là độ cao nhỏ nhất trong đoạn từ đến . Vì nên nếu thì ta hoàn toàn có thể nhảy từ tòa nhà sang tòa nhà .
Do đó ta xây dựng đồ thị có cạnh nối giữa tòa nhà với tòa nhà
Khi đã xây dựng được đồ thị thì có thể quy hoạch động hoặc sử dụng thuật toán tìm đường đi ngắn nhất để tính số lần nhảy ít nhất.
¶ Cài đặt
Xây dựng mảng L
/* L[k]: Xa nhất về bên trái nhận H[k] là max */
dq.clear();
for (int k = 1; k <= N; ++k) {
while (dq.size() && H[dq.front()] <= H[k]) dq.pop_front();
if (dq.size()) L[k] = dq.front() + 1;
else L[k] = k;
dq.push_front(k);
}
Xây dựng mảng R
/* R[k]: Xa nhất về bên phải nhận H[k] là max */
dq.clear();
for (int k = N; k >= 1; --k) {
while (dq.size() && H[dq.front()] <= H[k]) dq.pop_front();
if (dq.size()) R[k] = dq.front() - 1;
else R[k] = k;
dq.push_front(k);
}
Xây dựng mảng l
/* l[k]: Xa nhất về bên trái nhận H[k] là min*/
dq.clear();
for (int k = 1; k <= N; ++k) {
while (dq.size() && H[dq.front()] >= H[k]) dq.pop_front();
if (dq.size()) l[k] = dq.front() + 1;
else l[k] = k;
dq.push_front(k);
}
Xây dựng mảng r
/* r[k]: Xa nhất về bên phải nhận H[k] là min */
dq.clear();
for (int k = N; k >= 1; --k) {
while (dq.size() && H[dq.front()] >= H[k]) dq.pop_front();
if (dq.size()) r[k] = dq.front() - 1;
else r[k] = k;
dq.push_front(k);
}
Xây dựng đồ thị
for (int i = 1; i <= N; ++i) G[i].push_back(i + 1);
for (int k = 1; k <= N; ++k) {
if (H[k] < min(H[L[k] - 1], H[R[k] + 1])) {
G[L[k] - 1].push_back(R[k] + 1);
}
}
for (int k = 1; k <= N; ++k) {
if (max(H[l[k] - 1], H[r[k] + 1]) < H[k]) {
G[l[k] - 1].push_back(r[k] + 1);
}
}
¶ Đánh giá
- Số cạnh tối đa trong bài toán này:
- Chi phí thời gian xây dựng 4 mảng là
- Chi phí thời gian thuật toán là