Hướng giải của Tìm Min-Max Động
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.
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ả:
Hướng dẫn giải: Tìm Min-Max Động
Phân tích bài toán
Yêu cầu quản lý một kho hàng cho phép chèn, xóa và tìm kiếm giá trị nhỏ nhất (Min) cũng như lớn nhất (Max) hiện tại.
Skip List là cấu trúc được sắp xếp sẵn, do đó:
- Phần tử nhỏ nhất luôn nằm ở đầu danh sách liên kết cấp 0 (sau nút Header).
- Phần tử lớn nhất nằm ở cuối danh sách liên kết cấp 0. Chúng ta có thể lấy nhanh trong \(O(1)\) hoặc \(O(\log N)\) tùy thuộc vào cách triển khai con trỏ đuôi (Tail Pointer).
Trong C++, cấu trúc dữ liệu std::multiset hỗ trợ đầy đủ các thao tác này trong thời gian \(O(\log N)\):
- Phần tử nhỏ nhất:
*s.begin() - Phần tử lớn nhất:
*s.rbegin()(hoặc*prev(s.end()))
Độ phức tạp
- Thời gian: \(O(\log N)\) cho mỗi thao tác.
- Không gian: \(O(N)\) bộ nhớ.
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, q;
if (!(cin >> n >> q)) return 0;
multiset<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x);
}
for (int i = 0; i < q; i++) {
int type;
cin >> type;
if (type == 1) {
int x;
cin >> x;
s.insert(x);
} else if (type == 2) {
int x;
cin >> x;
auto it = s.find(x);
if (it != s.end()) {
s.erase(it);
}
} else if (type == 3) {
if (s.empty()) {
cout << -1 << "\n";
} else {
cout << *s.begin() << "\n";
}
} else if (type == 4) {
if (s.empty()) {
cout << -1 << "\n";
} else {
cout << *s.rbegin() << "\n";
}
}
}
return 0;
}
Nhận xét