Hướng dẫn giải của [200 đề thầy Đức] Bài 179: Đoạn con có giá trị nhỏ nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy n số nguyên dương và số k. Với mỗi đoạn k phần tử liên tiếp, in ra giá trị nhỏ nhất của đoạn đó, mỗi đoạn một dòng. Có n - k + 1 đoạn, với n ≤ 10^3.
Sub 1: Vét cạn — ~O(N·K)~
Với mỗi đoạn [i, i+k-1], quét toàn bộ k phần tử để tìm giá trị nhỏ nhất. Cách này đúng và với N ≤ 1000 chạy nhanh, đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: với mỗi đoạn k phần tử, quét cả đoạn để tìm giá trị nhỏ nhất
for (int i = 0; i + k <= n; i++) {
int mn = a[i];
for (int j = i; j < i + k; j++) mn = min(mn, a[j]);
cout << mn << "\n";
}
return 0;
}
Sub 2: Deque đơn điệu (sliding window minimum) — ~O(N)~
Dùng một hàng đợi hai đầu (deque) lưu chỉ số các phần tử theo giá trị tăng dần:
- Khi thêm
a[i], xóa ở cuối các chỉ số có giá trị lớn hơn hoặc bằnga[i], vìa[i]nhỏ hơn và còn tồn tại lâu hơn nên các phần tử đó không bao giờ là đáp án nữa. - Xóa ở đầu các chỉ số đã nằm ngoài cửa sổ (
≤ i - k). - Khi đã đủ
kphần tử (i ≥ k - 1), đầu deque là chỉ số có giá trị nhỏ nhất của đoạn hiện tại.
Mỗi chỉ số vào và ra deque nhiều nhất một lần nên tổng thời gian là O(N). Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Dùng deque lưu chỉ số theo thứ tự giá trị tăng dần.
// Đầu deque luôn là chỉ số có giá trị nhỏ nhất trong cửa sổ hiện tại.
deque<int> dq;
for (int i = 0; i < n; i++) {
// Bỏ chỉ số đã ra khỏi cửa sổ (ở đầu)
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
// Bỏ các giá trị ở cuối lớn hơn hoặc bằng a[i], vì a[i] tốt hơn và sống lâu hơn
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) cout << a[dq.front()] << "\n";
}
return 0;
}
Bình luận