Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm tổng các trung bình của mọi danh sách con có độ dài lẻ của danh sách đã cho.
Vì vậy, nếu đầu vào là nums =[2, 4, 6, 3], thì đầu ra sẽ là 23, vì danh sách con có độ dài lẻ là - [2], [4], [6], [3], [2, 4, 6], [4, 6, 3], do đó, tổng của các phương tiện là 2 + 4 + 6 + 3 + 4 + 4 =23
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=0
-
để khởi tạo i:=0, khi tôi
-
xác định hàng đợi ưu tiên được gọi là que_max
-
xác định một hàng đợi ưu tiên khác được gọi là que_min
-
để khởi tạo j:=i, khi j
-
chèn nums [j] vào que_max
-
trong khi kích thước que_max> =2, do -
-
chèn phần tử hàng đầu của que_max vào que_min
-
xóa phần tử trên cùng khỏi que_max
-
-
while (kích thước của que_min không phải là 0 và phần tử trên cùng của que_max> phần tử trên cùng của que_min), do -
-
a:=phần tử trên cùng của que_max, xóa phần tử trên cùng khỏi que_max
-
b:=phần tử trên cùng của que_min, xóa phần tử trên cùng khỏi que_min
-
chèn b vào que_max
-
chèn một vào que_min
-
-
nếu tôi mod 2 giống với j mod 2, thì -
-
ret:=ret + phần tử trên cùng của que_max
-
-
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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