Hướng giải của Tổng Max Min Của Cửa Sổ

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ính tổng các giá trị \((\max + \min)\) của mọi cửa sổ trượt kích thước \(K\). Ta kết hợp thuật toán tìm Max và tìm Min bằng cách duy trì đồng thời hai Deque đơn điệu song song:

  • max_dq: duy trì chỉ số các phần tử giảm dần (để lấy max tại max_dq.front()).
  • min_dq: duy trì chỉ số các phần tử tăng dần (để lấy min tại min_dq.front()).

Tại mỗi bước trượt \(i \ge K - 1\), ta cộng dồn giá trị a[max_dq.front()] + a[min_dq.front()] vào biến tổng tích lũy.

Lưu ý: Tổng tích lũy có thể rất lớn và vượt quá giới hạn số nguyên 32-bit, vì vậy cần dùng kiểu dữ liệu long long để tránh tràn số.

Độ 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<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<int> max_dq, min_dq;
    long long total_sum = 0;

    for (int i = 0; i < n; i++) {
        // Cập nhật max_dq
        while (!max_dq.empty() && max_dq.front() <= i - k) {
            max_dq.pop_front();
        }
        while (!max_dq.empty() && a[max_dq.back()] <= a[i]) {
            max_dq.pop_back();
        }
        max_dq.push_back(i);

        // Cập nhật min_dq
        while (!min_dq.empty() && min_dq.front() <= i - k) {
            min_dq.pop_front();
        }
        while (!min_dq.empty() && a[min_dq.back()] >= a[i]) {
            min_dq.pop_back();
        }
        min_dq.push_back(i);

        // Cộng dồn kết quả
        if (i >= k - 1) {
            total_sum += a[max_dq.front()] + a[min_dq.front()];
        }
    }

    cout << total_sum << "\n";
    return 0;
}

Nhận xét

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