Giả sử ta có danh sách nums, ta phải tìm tổng trung vị của mọi dãy con độ dài lẻ của nums.
Ví dụ: nums = [2, 4, 6, 3], đầu ra = 23. Các dãy con độ dài lẻ: [2], [4], [6], [3], [2,4,6], [4,6,3]. Trung vị: 2+4+6+3+4+4=23.
Để giải quyết, ta dùng hai priority queue (max-heap và min-heap) để duy trì trung vị khi mở rộng dãy con:
- ret := 0.
- for i từ 0 đến n-1:
- Khởi tạo que_max (max-heap) và que_min (min-heap).
- for j từ i đến n-1:
- Chèn nums[j] vào que_max.
- Cân bằng hai heap: nếu que_max.size() - que_min.size() >= 2, chuyển đỉnh que_max sang que_min.
- Đảm bảo đỉnh que_max <= đỉnh que_min, nếu vi phạm thì hoán đổi đỉnh.
- Nếu i%2 == j%2 (độ dài lẻ): ret += que_max.top().
- Trả về ret.
Xem triển khai dưới đây:
Ví dụ
#include <bits/stdc++.h> using namespace std; int solve(vector<int>& nums) { int ret = 0; for (int i = 0; i < nums.size(); i++) { priority_queue<int> que_max; priority_queue<int, vector<int>, greater<int>> que_min; for (int j = i; j < nums.size(); j++) { que_max.push(nums[j]); while (que_max.size() - que_min.size() >= 2) { que_min.push(que_max.top()); que_max.pop(); } while (que_min.size() && que_max.top() > que_min.top()) { int a = que_max.top(); que_max.pop(); int b = que_min.top(); que_min.pop(); que_max.push(b); que_min.push(a); } if (i % 2 == j % 2) { ret += que_max.top(); } } } return ret; } int main(){ vector<int> v = {2, 4, 6, 3}; cout << solve(v); }
Đầu vào
{2, 4, 6, 3}
Đầu ra
23