এই সমস্যায়, আমাদেরকে N পূর্ণসংখ্যার একটি অ্যারে [] এবং একটি পূর্ণসংখ্যা 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 সমাধান পদ্ধতি
ধারণা হল অ্যারের সর্বাধিক খুঁজে বের করা এবং তারপর maxSum যোগ করার পরে এটি হ্রাস করা। এই প্রক্রিয়াটি k বার পুনরাবৃত্তি করলে ফলাফল পাওয়া যায়।
অ্যারের সর্বাধিক উপাদান খুঁজে বের করার জন্য, একাধিক উপায় হতে পারে এবং সবচেয়ে প্রতিশ্রুতিশীলটি হল সর্বাধিক হিপ ডেটা স্ট্রাকচার ব্যবহার করা৷
সুতরাং, আমরা অ্যারের সমস্ত উপাদান একটি সর্বাধিক হিপে সন্নিবেশ করব, হিপের সর্বাধিক উপাদানটি এটির মূলে উপস্থাপন করা হয়েছে। আমরা এটি মুছে ফেলব, maxSum-এ যোগ করব এবং হিপে ফিরে (এলিমেন্ট -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
