সর্বাধিক উপাদান যা C++ এ k আপডেটের সাথে সমান করা যেতে পারে

প্রদত্ত কাজটি হল সর্বাধিক সংখ্যক উপাদান খুঁজে বের করা যা একটি প্রদত্ত অ্যারেতে এর উপাদানগুলিকে সর্বাধিক k বার বৃদ্ধি করার পরে সমান করা যায়৷

আসুন এখন বুঝতে পারি একটি উদাহরণ ব্যবহার করে আমাদের কী করতে হবে −

ইনপুট

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

আউটপুট

ব্যাখ্যা

এখানে আমরা 1কে তিনবার বৃদ্ধি করে এবং 3টি চারবার বৃদ্ধি করে দুটি চার পেতে পারি, যা একটি [] ={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<=আকার পর্যন্ত লুপ করুন এবং p[i] =0 এবং m[i] =0 শুরু করুন।
লুপের বাইরে m[0] =arr[0] এবং p[0] =arr[0] রাখুন।
i =1 থেকে i
লুপের পরে, int Lt =1, Rt =আকার, যথাক্রমে বাম মান, ডান মান এবং চূড়ান্ত উত্তর সংরক্ষণের ফলাফল শুরু করুন। এর পরে বাইনারি অনুসন্ধান শুরু করুন।
শর্ত সহ লুপ করার সময় শুরু করুন (Lt
অন্যথায় কেবল Rt =মধ্য -1 লিখুন।
লুপ প্রিন্ট ফলাফলের বাইরে।
(int i =0, j =x; j <=size;j++, i++)
এর জন্য শর্ত সহ বুলে EleCal() লুপের জন্য ফাংশন শুরু করুন।
লুপের ভিতরে চেক করুন যদি (x * m[j] - (p[j] - p[i]) <=k)। যদি তাই হয়, তারপর সত্য ফিরে. লুপের বাইরে মিথ্যা রিটার্ন।

উদাহরণ

#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;
}