ধরুন আমাদের কাছে সংখ্যা বলা সংখ্যার একটি তালিকা আছে, আমাদের প্রদত্ত তালিকার প্রতিটি বিজোড়-দৈর্ঘ্যের সাবলিস্টের মধ্যকগুলির যোগফল খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[2, 4, 6, 3], তাহলে আউটপুট হবে 23, যেমন বিজোড় দৈর্ঘ্যের সাবলিস্টগুলি হল − [2], [4], [6], [3], [2, 4, 6], [4, 6, 3], সুতরাং মধ্যকার যোগফল হল 2 + 4 + 6 + 3 + 4 + 4 =23
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0
-
আরম্ভ করার জন্য i :=0, যখন i <সংখ্যার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
que_max
নামক অগ্রাধিকার সারি সংজ্ঞায়িত করুন -
que_min
নামে আরেকটি অগ্রাধিকার সারি সংজ্ঞায়িত করুন -
j শুরু করার জন্য :=i, যখন j <সংখ্যার আকার, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
-
que_max
-এ nums[j] ঢোকান -
যখন que_max>=2 এর আকার, −
করুন-
que_min
-এ que_max-এর শীর্ষ উপাদান সন্নিবেশ করান -
que_max
থেকে শীর্ষ উপাদান মুছুন
-
-
যখন (que_min এর আকার 0 নয় এবং que_max এর শীর্ষ উপাদান> que_min এর শীর্ষ উপাদান), করুন −
-
a :=que_max এর শীর্ষ উপাদান, que_max থেকে শীর্ষ উপাদান মুছুন
-
b :=que_min এর শীর্ষ উপাদান, que_min থেকে শীর্ষ উপাদান মুছুন
-
que_max
-এ b সন্নিবেশ করান -
que_min
-এ একটি ঢোকান
-
-
যদি i mod 2 j mod 2 এর মত হয়, তাহলে −
-
ret :=ret + que_max
এর শীর্ষ উপাদান
-
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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} আউটপুট
23
