Hướng giải của Chênh Lệch Giới Hạn

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 tìm độ dài đoạn con liên tiếp dài nhất sao cho hiệu giữa giá trị lớn nhất và nhỏ nhất trong đoạn \(\le T\). Để giải bài toán này với độ phức tạp \(O(N)\), ta sử dụng kỹ thuật cửa sổ trượt di động \([l, r]\) kết hợp hai Deque đơn điệu chạy song song:

  • max_dq: duy trì các giá trị lớn nhất giảm dần.
  • min_dq: duy trì các giá trị nhỏ nhất tăng dần.

Thuật toán:

  1. Di chuyển con trỏ phải r từ \(0\) đến \(N-1\) và đẩy \(a[r]\) vào cả hai deque tương tự thuật toán tìm max/min cửa sổ trượt.
  2. Sau khi thêm \(a[r]\), nếu chênh lệch giữa phần tử lớn nhất và nhỏ nhất trong cửa sổ hiện tại (lấy từ đầu của hai deque: a[max_dq.front()] - a[min_dq.front()]) vượt quá \(T\):
    • Ta cần thu hẹp cửa sổ bằng cách tăng con trỏ trái l.
    • Nếu chỉ số ở đầu deque nhỏ hơn l, ta pop nó ra khỏi deque tương ứng.
  3. Khi cửa sổ hợp lệ, ta cập nhật độ dài cực đại tìm được: ans = max(ans, r - l + 1).

Độ phức tạp thời gian: \(O(N)\) do mỗi phần tử chỉ vào/ra deque tối đa 1 lầ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;
    long long t;
    if (!(cin >> n >> t)) return 0;

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

    deque<int> max_dq, min_dq;
    int max_len = 0;
    int l = 0;

    for (int r = 0; r < n; r++) {
        // Cập nhật max_dq (giảm dần)
        while (!max_dq.empty() && a[max_dq.back()] <= a[r]) {
            max_dq.pop_back();
        }
        max_dq.push_back(r);

        // Cập nhật min_dq (tăng dần)
        while (!min_dq.empty() && a[min_dq.back()] >= a[r]) {
            min_dq.pop_back();
        }
        min_dq.push_back(r);

        // Kiểm tra điều kiện hiệu max - min <= T
        while (!max_dq.empty() && !min_dq.empty() && a[max_dq.front()] - a[min_dq.front()] > t) {
            l++;
            if (max_dq.front() < l) max_dq.pop_front();
            if (min_dq.front() < l) min_dq.pop_front();
        }

        max_len = max(max_len, r - l + 1);
    }

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

Nhận xét

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