Hướng giải của Trung Vị Trượ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: Trung Vị Trượt

Phân tích bài toán

Bài toán yêu cầu tìm số trung vị trong mọi cửa sổ trượt kích thước \(K\) của mảng \(A\).

Một giải pháp kinh điển và tối ưu cho bài toán này là duy trì hai tập đa tập (multisets):

  1. lower_half: lưu trữ một nửa số lượng phần tử nhỏ hơn (kích thước luôn bằng \((K+1)/2\)). Phần tử lớn nhất ở đây là *lower_half.rbegin().
  2. upper_half: lưu trữ một nửa số lượng phần tử lớn hơn (kích thước luôn bằng \(K/2\)). Phần tử nhỏ nhất ở đây là *upper_half.begin().
Quy trình trượt cửa sổ
  • Khi chèn thêm một phần tử \(x\) mới:
    • Nếu \(x\) nhỏ hơn hoặc bằng phần tử lớn nhất trong lower_half, ta thêm \(x\) vào lower_half.
    • Ngược lại, thêm \(x\) vào upper_half.
    • Tiến hành tái cân bằng hai nửa bằng cách chuyển phần tử lớn nhất từ lower_half sang upper_half hoặc ngược lại cho đến khi kích thước thỏa mãn điều kiện mong muốn.
  • Khi loại bỏ phần tử cũ ra khỏi cửa sổ:
    • So sánh phần tử cần xóa với phần tử lớn nhất của lower_half để quyết định xóa từ bên nào.
    • Sử dụng hàm s.find() và thực hiện xóa thông qua iterator để chỉ xóa đúng một phần tử trùng lặp (tránh dùng s.erase(val) vì lệnh này sẽ xóa sạch toàn bộ các giá trị trùng).
    • Tái cân bằng lại hai nửa.
Độ phức tạp
  • Thời gian: \(O(N \log K)\) do mỗi phần tử được thêm và xóa đúng 1 lần trên cấu trúc multiset/Skip List.
  • Không gian: \(O(K)\) bộ nhớ để lưu trữ các phần tử trong cửa sổ hiện tại.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

multiset<int> lower_half;
multiset<int> upper_half;
int k;

void balance() {
    int cur_sz = lower_half.size() + upper_half.size();
    int target_lower = (cur_sz + 1) / 2;
    if (lower_half.size() > target_lower) {
        auto it = prev(lower_half.end());
        upper_half.insert(*it);
        lower_half.erase(it);
    } else if (lower_half.size() < target_lower) {
        auto it = upper_half.begin();
        lower_half.insert(*it);
        upper_half.erase(it);
    }
}

void insert_val(int x) {
    if (lower_half.empty() || x <= *lower_half.rbegin()) {
        lower_half.insert(x);
    } else {
        upper_half.insert(x);
    }
    balance();
}

void erase_val(int x) {
    auto it = lower_half.find(x);
    if (it != lower_half.end()) {
        lower_half.erase(it);
    } else {
        auto it2 = upper_half.find(x);
        if (it2 != upper_half.end()) {
            upper_half.erase(it2);
        }
    }
    balance();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < k; i++) {
        insert_val(a[i]);
    }

    cout << *lower_half.rbegin();
    for (int i = k; i < n; i++) {
        insert_val(a[i]);
        erase_val(a[i - k]);
        cout << " " << *lower_half.rbegin();
    }
    cout << "\n";
    return 0;
}

Nhận xét

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