सी ++ में प्रत्येक एक्सेस के बाद अधिकतम कमी होने पर सरणी से अधिकतम

इस समस्या में, हमें एक सरणी गिरफ्तारी [] और एक पूर्णांक एम दिया जाता है। हमारा कार्य सी ++ में प्रत्येक पहुंच के बाद अधिकतम कमी होने पर सरणी से अधिकतम खोजने के लिए एक प्रोग्राम बनाना है।

समस्या का विवरण

अधिकतम खोजने के लिए, हम सरणी से और प्रत्येक पुनर्प्राप्ति के बाद अधिकतम तत्व पाएंगे और इसे -1, Mtimes से घटा देंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट :गिरफ्तारी [] ={3, 6, 8, 9} एम =2

आउटपुट :17

स्पष्टीकरण

पहला पुनरावृत्ति, अधिकतम =9, योग =9, अद्यतन गिरफ्तारी ={3, 6, 8, 8}

दूसरा पुनरावृत्ति, अधिकतम =8, योग =9+8 =17, अद्यतन गिरफ्तारी ={3, 6, 7, 8}

समाधान दृष्टिकोण

अधिकतम ढेर का उपयोग करना एक आसान समाधान है जिसमें अधिकतम तत्व जड़ होगा। फिर रूट को पॉप करें, इसे 1 से घटाएं, फिर तत्व को फिर से डालें। यह पॉप और इंसर्ट M बार किया जाता है। प्रत्येक पॉप ऑपरेशन के लिए, हम तत्व को योग तत्व में जोड़ देंगे और एम पुनरावृत्तियों के बाद योग प्रिंट करेंगे।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[], int N, int M) {
   int sumVal = 0;
   priority_queue<int> heap;
   for (int i = 0; i < N; i++)
      heap.push(arr[i]);
   while (M--) {
      int maximumVal = heap.top();
      sumVal += maximumVal;
      heap.pop();
      heap.push(maximumVal - 1);
   }
   return sumVal;
}
int main() {
   int arr[] = { 3, 6, 8, 9};
   int M = 2;
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum from array when the maximum decrements after every access is "<<getSum(arr, N,M);
}

आउटपुट

The maximum from array when the maximum decrements after every access is 17