Hướng dẫn giải của Thao tác với hàng đợi ưu tiên


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hang7112, mattroinho, nquang2909

Editorial for pqueue: Thao tác với hàng đợi ưu tiên

Hiểu bài toán

Bài toán mô phỏng một hàng đợi ưu tiên (priority queue) với giới hạn dung lượng 15,000 phần tử. Có hai loại thao tác:

  1. +V: Thêm phần tử V vào danh sách nếu số lượng phần tử hiện tại < 15,000.
  2. -: Xóa tất cả các phần tử có giá trị lớn nhất khỏi danh sách (nếu danh sách không rỗng). Sau khi thực hiện N thao tác, cần liệt kê các phần tử còn lại theo thứ tự giảm dần.

Giới hạn: N ≤ 100,000, giá trị V ≤ 10^9.

Các cách tiếp cận

Cách Mô phỏng bằng Multiset (C++ Standard Library)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    multiset<long long> ms;

    while (n--) {
        char c;
        cin >> c;
        if (c == '+') {
            long long v;
            cin >> v;
            if (ms.size() < 15000) {
                ms.insert(v);
            }
        } else if (c == '-') {
            if (!ms.empty()) {
                // Lấy giá trị lớn nhất
                auto it = prev(ms.end());
                long long max_val = *it;
                // Xóa tất cả các phần tử có giá trị đó
                ms.erase(max_val);
            }
        }
    }

    // In kết quả theo thứ tự giảm dần
    cout << ms.size() << "\n";
    if (ms.empty()) return 0;

    for (auto it = ms.rbegin(); it != ms.rend(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";

    return 0;
}
  • Time Complexity: O(N log M), với M là số lượng phần tử trong multiset (M ≤ 15000). Các thao tác insert, erase, tìm max đều mất O(log M).
  • Space Complexity: O(M), lưu trữ tối đa 15000 phần tử.

Sử dụng std::multiset để lưu trữ các phần tử. Multiset tự động sắp xếp tăng dần và cho phép các giá trị trùng lặp.

  • Thao tác +V: Kiểm tra size() < 15000 rồi gọi insert(V).
  • Thao tác -: Kiểm tra !empty(), dùng rbegin() để lấy giá trị lớn nhất (hoặc prev(ms.end())), sau đó dùng erase(value) để xóa tất cả các phần tử có giá trị đó.
  • Xuất ra: Duyệt ngược lại từ rbegin() đến rend() để có thứ tự giảm dần. Độ phức tạp là O(N log M) do mỗi thao tác insert/erase mất O(log M).
Cách Mô phỏng bằng Vector và Sắp xếp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<long long> v;

    while (n--) {
        char c;
        cin >> c;
        if (c == '+') {
            long long val;
            cin >> val;
            if (v.size() < 15000) {
                v.push_back(val);
            }
        } else if (c == '-') {
            if (!v.empty()) {
                // Sắp xếp để tìm max
                sort(v.begin(), v.end());
                long long max_val = v.back();
                // Xóa các phần tử max ở cuối
                while (!v.empty() && v.back() == max_val) {
                    v.pop_back();
                }
            }
        }
    }

    // Sắp xếp giảm dần để in
    sort(v.begin(), v.end(), greater<long long>());

    // Loại bỏ trùng lặp (nếu cần yêu cầu chỉ in các giá trị duy nhất)
    // Đề bài yêu cầu 'liệt kê các phần tử còn lại', thường hiểu là in cả trùng lặp.
    // Tuy nhiên, sample output chỉ in các giá trị duy nhất (8 7 2 1).
    // Nếu in cả trùng lặp, kết quả với sample sẽ là 8 7 3 3 2 1.
    // Giả sử chỉ in giá trị duy nhất như các solution đã cho:

    cout << v.size() << "\n"; // Lưu ý: size này cần loại trùng nếu chỉ in duy nhất

    if (v.empty()) return 0;

    vector<long long> unique_res;
    if (!v.empty()) {
        unique_res.push_back(v[0]);
        for (size_t i = 1; i < v.size(); ++i) {
            if (v[i] != v[i-1]) {
                unique_res.push_back(v[i]);
            }
        }
    }

    // In kết quả
    cout << unique_res.size() << "\n";
    for (long long x : unique_res) cout << x << " ";
    cout << "\n";

    return 0;
}
  • Time Complexity: O(K log K) mỗi thao tác xóa (với K là số phần tử hiện tại), tổng thể có thể lên tới O(N * M log M) nếu xóa thường xuyên. Thao tác thêm O(1).
  • Space Complexity: O(M), tối đa 15000 phần tử.

Sử dụng vector để lưu trữ.

  • Thêm: push_back.
  • Xóa: Phải sort vector để đưa các phần tử giống nhau về gần nhau, sau đó xóa các phần tử ở cuối (vì sort mặc định tăng dần, phần tử max nằm ở cuối). Cách này rất chậm do phải sort lại mỗi lần xóa.
  • Lưu ý: Output sample cho thấy các giá trị được in là duy nhất. Do đó cần xử lý loại bỏ phần tử trùng lặp trước khi in (hoặc chỉ in các phần tử duy nhất). Cách này chỉ hiệu quả khi số lượng xóa ít, nhưng trong bài toán này số lần xóa có thể nhiều.
Cách Mô phỏng bằng Priority Queue (Max Heap)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    priority_queue<long long> pq; // Max Heap

    while (n--) {
        char c;
        cin >> c;
        if (c == '+') {
            long long v;
            cin >> v;
            if (pq.size() < 15000) {
                pq.push(v);
            }
        } else if (c == '-') {
            if (!pq.empty()) {
                long long mx = pq.top();
                // Xóa tất cả các phần tử có giá trị bằng mx
                // Do priority_queue không hỗ trợ xóa theo giá trị, ta phải dùng một buffer
                // Hoặc đơn giản là pop cho đến khi giá trị thay đổi
                // Tuy nhiên, priority_queue không thể truy cập bên trong.
                // Giải pháp: Dùng multiset hoặc xóa thủ công.
                // Với PQ, ta chỉ có thể pop từng phần tử.
                // Nếu chỉ cần xóa max hiện tại, ta pop 1 lần.
                // Nhưng bài này xóa TẤT CẢ các phần tử max.
                // Ta cần pop hết các phần tử giống mx.
            }
        }
    }
    // ...
    return 0;
}
  • Time Complexity: O(N log M)
  • Space Complexity: O(M)

Sử dụng priority_queue (Max Heap).

  • Thêm: push(v).
  • Xóa: Lấy top() (max). Tuy nhiên, để xóa tất cả các phần tử có giá trị bằng max, ta phải pop từng phần tử, kiểm tra giá trị, và lưu vào một vector tạm nếu giá trị khác. Sau đó push lại các giá trị khác vào heap.
  • Hoặc hiệu quả hơn: Dùng multiset như Approach 1. Approach này trong code mẫu không được đề xuất cao bằng multiset do việc xóa hàng loạt bất tiện.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N log M), với M là số lượng phần tử trong multiset (M ≤ 15000). Các thao tác insert, erase, tìm max đều mất O(log M). O(M), lưu trữ tối đa 15000 phần tử. Mô phỏng bằng Multiset (C++ Standard Library)
2 O(K log K) mỗi thao tác xóa (với K là số phần tử hiện tại), tổng thể có thể lên tới O(N * M log M) nếu xóa thường xuyên. Thao tác thêm O(1). O(M), tối đa 15000 phần tử. Mô phỏng bằng Vector và Sắp xếp
3 O(N log M) O(M) Mô phỏng bằng Priority Queue (Max Heap)

Bài học kinh nghiệm

  • Vấn đề chính là duy trì một cấu trúc dữ liệu cho phép thêm phần tử, tìm phần tử lớn nhất, và xóa tất cả các phần tử có giá trị lớn nhất đó một cách hiệu quả.
  • Multiset (C++) là lựa chọn tối ưu nhất vì nó hỗ trợ sắp xếp tự động, cho phép xóa theo giá trị (xóa tất cả các phần tử có giá trị V bằng erase(V)) và có độ phức tạp logarithmic.
  • Đề bài yêu cầu in các phần tử còn lại theo thứ tự giảm dần và chỉ in các giá trị duy nhất (dựa trên sample). Do đó, sau khi xử lý thao tác, ta cần loại bỏ trùng lặp trước khi in.

Lỗi thường gặp

  • Xử lý sai giới hạn 15000 phần tử: Phải kiểm tra kích thước trước khi thêm.
  • Quên xử lý trường hợp danh sách rỗng khi thực hiện thao tác xóa '-'.
  • Lỗi logic khi xóa phần tử lớn nhất: Phải xóa TẤT CẢ các phần tử có giá trị lớn nhất, không chỉ xóa một phần tử.
  • Sai thứ tự in ra: Đề bài yêu cầu giảm dần, nhưng các cấu trúc dữ liệu mặc định (vector, multiset) thường duyệt tăng dần. Cần duyệt ngược lại (rbegin/rend).

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.