C++-এ k আপডেট দিয়ে ম্যাক্সিমাম এলিমেন্ট সমান করা

দেওয়া কাজ হচ্ছে একটি অ্যারেতে সর্বোচ্চ কতগুলো এলিমেন্ট সমান করা যায় সর্বোচ্চ k বার ইনক্রিমেন্ট করার পর।

উদাহরণ দিয়ে বুঝি −

ইনপুট

a[] = {1, 3, 8}, k = 4

আউটপুট

ব্যাখ্যা

এখানে আমরা দুটি ৪ বানাতে পারি ১ কে তিনবার এবং ৩ কে চারবার ইনক্রিমেন্ট করে, যা a[] = {4, 4, 8} বানায়।

ইনপুট

arr = {2, 5, 9}, k = 2

আউটপুট

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

main() ফাংশনে int a[], size এবং k ইনিশিয়ালাইজ করা হয়েছে অ্যারে এলিমেন্ট, আকার এবং সর্বোচ্চ আপডেট সংরক্ষণের জন্য।
Max() ফাংশনে, প্রথমে অ্যারেটি ক্রমবর্ধমান ক্রমে সর্ট করা হয় এবং তারপর দুটি আরো অ্যারে int p[size + 1] এবং m[size + 1] ডিক্লেয়ার করা হয় যা প্রিফিক্স সম এবং ম্যাক্সিমাম মান সংরক্ষণ করবে।
i = 0 থেকে i<= size পর্যন্ত লুপ করে p[i] = 0 এবং m[i] = 0 ইনিশিয়ালাইজ।
লুপের বাইরে m[0] = arr[0] এবং p[0] = arr[0]।
i = 1 থেকে i<size পর্যন্ত লুপ করে p[i] = p[i - 1] + arr[i] প্রিফিক্স সম ক্যালকুলেট এবং m[i] = max(m[i - 1], arr[i]) সেটি পজিশন পর্যন্ত ম্যাক্সিমাম মান ক্যালকুলেট।
লুপের পর, int Lt = 1, Rt = size, result ডিক্লেয়ার করা হয় বাম মান, ডান মান এবং চূড়ান্ত উত্তর সংরক্ষণের জন্য। তারপর বাইনারি সার্চ শুরু।
while লুপ কন্ডিশন (Lt < Rt)। লুপের ভিতরে int mid = (Lt + Rt) / 2। চেক করা হয় (EleCal(p, m, mid - 1, k, size))। যদি সত্য হয়, তবে result = mid এবং Lt = mid +1।
অন্যথায় Rt = mid -1।
লুপের বাইরে result প্রিন্ট।
bool EleCal() ফাংশনে for লুপ কন্ডিশন for (int i = 0, j = x; j <= size; j++, i++)।
লুপের ভিতরে চেক করা হয় (x * m[j] - (p[j] - p[i]) <= k)। যদি সত্য হয়, তবে true রিটার্ন। লুপের বাইরে false রিটার্ন।

উদাহরণ

#include <bits/stdc++.h> 
using namespace std; 

bool EleCal(int p[], int m[], int x, int k, int size){ 
    for (int i = 0, j = x; j <= size; j++, i++){ 
        if (x * m[j] - (p[j] - p[i]) <= k) 
            return true; 
    } 
    return false; 
} 

void Max(int arr[], int size, int k){ 
    // sorting array in ascending order 
    sort(arr, arr + size); 
    int p[size + 1]; 
    //array for maximum value 
    int m[size + 1]; 
    // Initialize prefix array and maximum array 
    for (int i = 0; i <= size; ++i){ 
        p[i] = 0; 
        m[i] = 0; 
    } 
    m[0] = arr[0]; 
    p[0] = arr[0]; 
    for (int i = 1; i < size; i++){ 
        // Calculating prefix sum of the array 
        p[i] = p[i - 1] + arr[i]; 
        // Calculating max value upto that position 
        // in the array 
        m[i] = max(m[i - 1], arr[i]); 
    } 
    // Binary seach 
    int Lt = 1, Rt = size, result; 
    while (Lt < Rt){ 
        int mid = (Lt + Rt) / 2; 
        if (EleCal(p, m, mid - 1, k, size)){ 
            result = mid; 
            Lt = mid + 1; 
        } 
        else 
            Rt = mid - 1; 
    } 
    //answer 
    cout<<result; 
} 
// main function 
int main(){ 
    int a[] = { 1, 3, 8 }; 
    int size = sizeof(a) / sizeof(a[0]); 
    int k = 4; 
    Max(a, size, k); 
    return 0; 
}