समस्या विवरण
इस समस्या में, हमें N पूर्णांकों का एक ऐरे arr[] और एक पूर्णांक m दिया गया है। हमारा कार्य ऐरे से मैक्सिमम ढूंढने का प्रोग्राम बनाना है जब प्रत्येक एक्सेस के बाद मैक्सिमम घटता है।
समस्या विवरण - हमें ऐरे के अधिकतम तत्वों का अधिकतम योग ढूंढना है और लिए गए मैक्स को k बार एक से घटाना है।
उदाहरण
arr[] = {3, 6, 7, 8, 8}, k = 3
आउटपुट
व्याख्या
पहला इटरेशन: अपडेट से पहले ऐरे = {3, 6, 7, 8, 8}, मैक्स = 8, योग = 8, अपडेट के बाद ऐरे = {3, 6, 7, 7, 8}
दूसरा इटरेशन: अपडेट से पहले ऐरे = {3, 6, 7, 7, 8}, मैक्स = 8, योग = 8 + 8 = 16, अपडेट के बाद ऐरे = {3, 6, 7, 7, 7}
तीसरा इटरेशन: अपडेट से पहले ऐरे = {3, 6, 7, 7, 7}, मैक्स = 7, योग = 16 + 7 = 23, अपडेट के बाद ऐरे = {3, 6, 6, 7, 7}
अधिकतम योग = 23
हल करने का दृष्टिकोण
विचार ऐरे का मैक्सिमम ढूंढना और उसे मैक्ससम में जोड़ने के बाद एक से घटाना है। इस प्रक्रिया को k बार दोहराने से परिणाम मिलता है।
ऐरे के अधिकतम तत्व को ढूंढने के लिए, कई तरीके हो सकते हैं और सबसे आशाजनक एक मैक्स हीप डेटा स्ट्रक्चर का उपयोग करना है।
तो, हम ऐरे के सभी तत्वों को मैक्स हीप में डालेंगे, हीप में अधिकतम तत्व इसके रूट पर दर्शाया जाता है। हम इसे हटाएंगे, मैक्ससम में जोड़ेंगे और (तत्व -1) को वापस हीप में डालेंगे। वांछित मैक्ससम पाने के लिए इसे k बार करें।
एल्गोरिदम
- आरंभीकरण - maxSum = 0
- चरण 1 - एक मैक्स हीप डेटा स्ट्रक्चर बनाएं और तत्वों को इसमें डालें।
- चरण 2 - i -> 0 से k तक लूप और चरण 3-5 का पालन करें।
- चरण 3 - रूट तत्व लें, maxVal = रूट और इसे पॉप करें।
- चरण 4 - maxVal को maxSum में जोड़ें, maxSum += maxVal
- चरण 5 - अपडेटेड maxVal को मैक्स हीप में डालें।
- चरण 6 - maxSum वापस करें।
उदाहरण
#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
