Hướng giải của Cửa Sổ Trượt Nhỏ Nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu tìm giá trị nhỏ nhất trong mỗi cửa sổ trượt kích thước \(K\). Tương tự như bài tìm giá trị lớn nhất, ta sử dụng deque để duy trì một Monotonic Queue nhưng theo thứ tự tăng dần của giá trị phần tử.

Quy trình xử lý với phần tử \(a[i]\):

  1. Loại bỏ các chỉ số đã trượt ra ngoài cửa sổ ở đầu deque (chỉ số \(\le i - K\)).
  2. Loại bỏ các chỉ số ở cuối deque nếu giá trị tương ứng lớn hơn hoặc bằng \(a[i]\), vì \(a[i]\) xuất hiện sau và nhỏ hơn sẽ luôn là lựa chọn tốt hơn các phần tử này trong tương lai.
  3. Thêm chỉ số \(i\) vào cuối deque.
  4. Giá trị nhỏ nhất trong cửa sổ luôn nằm ở đầu deque (a[dq.front()]).

Độ phức tạp thời gian: \(O(N)\).

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<int> dq;
    for (int i = 0; i < n; i++) {
        // Loại bỏ phần tử đã ra ngoài cửa sổ
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Loại bỏ phần tử lớn hơn phần tử hiện tại
        while (!dq.empty() && a[dq.back()] >= a[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // In kết quả
        if (i >= k - 1) {
            cout << a[dq.front()] << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.