मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहते हैं, हमें दी गई सूची की प्रत्येक विषम-लंबाई वाली उप-सूची के माध्यकों का योग ज्ञात करना होगा।
इसलिए, यदि इनपुट संख्या =[2, 4, 6, 3] की तरह है, तो आउटपुट 23 होगा, क्योंकि विषम-लंबाई वाले सबलिस्ट हैं - [2], [4], [6], [3], [2, 4, 6], [4, 6, 3], इसलिए माध्यिकाओं का योग 2 + 4 + 6 + 3 + 4 + 4 =23 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0
-
इनिशियलाइज़ i :=0 के लिए, जब i <अंकों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -
-
प्राथमिकता कतार को परिभाषित करें जिसे que_max कहा जाता है
-
que_min नामक एक अन्य प्राथमिकता कतार को परिभाषित करें
-
इनिशियलाइज़ j :=i के लिए, जब j <अंकों का आकार, अपडेट करें (j को 1 से बढ़ाएँ), करें -
-
que_max में nums[j] डालें
-
जबकि que_max>=2 का आकार, करें -
-
que_max के शीर्ष तत्व को que_min में डालें
-
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 के समान है, तो -
-
रिट :=रिट + 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