इस समस्या में, हमें N पूर्णांकों का एक सरणी arr[] और एक पूर्णांक m दिया जाता है। हमारा काम हर एक्सेस के बाद अधिकतम घटने पर ऐरे से मैक्सिमम को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - हमें सरणी के अधिकतम तत्वों का अधिकतम योग ज्ञात करना होगा और अधिकतम को एक k गुना कम करना होगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {3, 6, 7, 8, 8}, k = 3 आउटपुट
स्पष्टीकरण
First iteration: array before = {3, 6, 7, 8, 8}, max = 8, sum = 8, array after update = {3, 6, 7, 7, 8}
Second iteration: array before = {3, 6, 7, 7, 8}, max = 8, sum = 8 + 8 = 16, array after update = {3, 6, 7, 7, 7}
Third iteration: array before = {3, 6, 7, 7, 7}, max = 7, sum = 16 + 7 = 23, array after update = {3, 6, 6, 7, 7}
Maximum sum = 23 समाधान दृष्टिकोण
विचार यह है कि अधिकतम सरणी का पता लगाया जाए और फिर मैक्ससम में जोड़ने के बाद इसे घटाया जाए। इस प्रक्रिया को k बार दोहराने से परिणाम मिलता है।
सरणी के अधिकतम तत्व को खोजने के लिए, कई तरीके हो सकते हैं और सबसे आशाजनक तरीका अधिकतम हीप डेटा संरचना का उपयोग करना है।
तो, हम सरणी के सभी तत्वों को अधिकतम ढेर में सम्मिलित करेंगे, ढेर में अधिकतम तत्व इसकी जड़ में दर्शाया गया है। हम इसे हटा देंगे, मैक्ससम में जोड़ देंगे और (तत्व -1) वापस ढेर में डाल देंगे। वांछित अधिकतम राशि प्राप्त करने के लिए इसे k बार करें।
एल्गोरिदम
आरंभ करें - मैक्ससम =0
चरण 1 - एक अधिकतम हीप डेटा संरचना बनाएं और उसमें तत्वों को पुश करें।
चरण 2 − i -> 0 से k के लिए लूप और सेट 3 - 5 का अनुसरण करें।
चरण 3 - मूल तत्व लें, maxVal =root और इसे पॉप करें।
चरण 4 − maxVal को maxSum में जोड़ें, maxSum +=maxVal
चरण 5 - अधिकतम हीप में अपडेटेड मैक्सवैल डालें।
चरण 6 - मैक्ससम लौटाएं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
long calcMaxSumDec(int arr[], int m, int n) {
long maxSum = 0;
long maxVal;
priority_queue<long> max_heap;
for (int i = 0; i < n; i++) {
max_heap.push(arr[i]);
}
for(int i = 0; i < m; i++) {
maxVal = max_heap.top();
maxSum += maxVal;
max_heap.pop();
max_heap.push(maxVal - 1);
}
return maxSum;
}
int main() {
int arr[] = { 2, 3, 5, 4 }, m = 3;
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximums from array when the maximum decrements after every access is "<<calcMaxSumDec(arr, m, n);
} आउटपुट
The maximums from array when the maximum decrements after every access is 13