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.
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ậpTác giả: , , ,
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:
+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.-: 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 trasize() < 15000rồi gọiinsert(V). - Thao tác
-: Kiểm tra!empty(), dùngrbegin()để lấy giá trị lớn nhất (hoặcprev(ms.end())), sau đó dùngerase(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()đếnrend()để 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
sortvector để đư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
multisetnhư 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