Hướng dẫn giải

Bài toán yêu cầu tìm số âm đầu tiên trong mỗi cửa sổ trượt kích thước \(K\). Ta có thể giải bài toán này bằng cách sử dụng một Deque để lưu trữ các chỉ số của các số âm trong mảng.

Thuật toán:

1. Duyệt mảng từ trái sang phải. Với mỗi phần tử \(a[i]\):
   • Nếu \(a[i] < 0\), ta thêm chỉ số \(i\) vào cuối deque.
   • Loại bỏ các chỉ số ở đầu deque nếu chúng đã vượt ra ngoài cửa sổ hiện tại (chỉ số \(\le i - K\)).
2. Khi cửa sổ đã đủ kích thước \(K\) (\(i \ge K - 1\)):
   • Nếu deque không rỗng, số âm đầu tiên chính là phần tử tại chỉ số ở đầu deque (a[dq.front()]).
   • Nếu deque rỗng, nghĩa là không có số âm nào trong cửa sổ này, kết quả ghi nhận là \(0\).

Độ phức tạp thời gian: \(O(N)\) Độ phức tạp không gian: \(O(N)\) trong trường hợp xấu nhất toàn số âm.

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; // Lưu chỉ số của các số âm
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            dq.push_back(i);
        }

        // Loại bỏ chỉ số đã ra ngoài cửa sổ
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

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