এই সমস্যায়, আমাদেরকে একটি অ্যারে অ্যারে[]এবং একটি পূর্ণসংখ্যা M দেওয়া হয়। আমাদের কাজ হল অ্যারে থেকে সর্বোচ্চ বের করার জন্য একটি প্রোগ্রাম তৈরি করা যখন C++ এ প্রতিটি অ্যাক্সেসের পরে সর্বাধিক হ্রাস পায়।
সমস্যা বর্ণনা
সর্বাধিক খুঁজে পেতে, আমরা অ্যারে থেকে সর্বাধিক উপাদানটি খুঁজে পাব এবং প্রতিটি পুনরুদ্ধারের পরে এটিকে -1, Mtimes দ্বারা হ্রাস করব৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :arr[] ={3, 6, 8, 9} M =2
আউটপুট :17
ব্যাখ্যা
1ম পুনরাবৃত্তি, সর্বোচ্চ =9, যোগফল =9, আপডেট করা arr ={3, 6, 8, 8}
২য় পুনরাবৃত্তি, সর্বোচ্চ =8, যোগফল =9+8 =17, আপডেট করা arr ={3, 6, 7, 8}
সমাধান পদ্ধতি
একটি সহজ সমাধান হল ম্যাক্স হিপ ব্যবহার করা যাতে ম্যাক্স এলিমেন্ট অ্যাট্রুট থাকবে। তারপর রুটটি পপ করুন, এটি 1 দ্বারা হ্রাস করুন, তারপর আবার উপাদানটি সন্নিবেশ করুন। এই পপ এবং সন্নিবেশ M বার করা হয়. প্রতিটি পপ অপারেশনের জন্য, আমরা যোগ এলিমেন্টে উপাদান যোগ করব এবং 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
