C++-এ সব বিজোড় দৈর্ঘ্যের সাবলিস্টের মিডিয়ানের যোগফল বের করুন

মান लीজিয়ে nums নামে একটি সংখ্যা লিস্ট আছে, আমাদের সব বিজোড় দৈর্ঘ্যের সাবলিস্টের মিডিয়ানের যোগফল বের করতে হবে।

যেমন ইনপুট nums = [2, 4, 6, 3] হলে আউটপুট হবে ২৩, কারণ বিজোড় দৈর্ঘ্যের সাবলিস্টগুলো: [2], [4], [6], [3], [2, 4, 6], [4, 6, 3], মিডিয়ানগুলোর যোগফল = 2 + 4 + 6 + 3 + 4 + 4 = 23

সমাধানের ধাপগুলো:

ret := 0
i=0 থেকে nums.size()-1 পর্যন্ত:

প্রাইরিটি কিউ que_max এবং que_min সংজ্ঞায়িত করুন
j=i থেকে nums.size()-1 পর্যন্ত:

nums[j] que_max-এ ইনসার্ট করুন
যখন que_max সাইজ >= 2, que_max-র টপ que_min-এ সরিয়ে que_max-র টপ ডিলিট করুন
যখন que_min খালি নয় এবং que_max-র টপ > que_min-র টপ, উভয় টপ অদলবদল করুন
যদি i%2 == j%2 হয়, ret += que_max-র টপ

ret রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

#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); 
}

ইনপুট

{2, 4, 6, 3}