C++ এ সর্বোচ্চ গড় সাবারে II

ধরুন আমাদের n পূর্ণসংখ্যা সহ একটি অ্যারে আছে, আমাদেরকে সংলগ্ন সাবয়ারে খুঁজে বের করতে হবে যার দৈর্ঘ্য k এর থেকে বেশি বা সমান যার সর্বোচ্চ গড় মান রয়েছে। আমাদের সর্বোচ্চ গড় মান খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট হয় [1,12,-5,-6,50,3], k =4, তাহলে আউটপুট হবে 12.75, যেমন দৈর্ঘ্য 5 হলে, সর্বোচ্চ গড় মান হবে 10.8, যখন দৈর্ঘ্য 6 হয়। , সর্বোচ্চ গড় মান হল 9.16667৷ সুতরাং আউটপুট হল 12.75।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন ঠিক করুন(), এটি x, একটি অ্যারে সংখ্যা, k,

  লাগবে

• n :=সংখ্যার আকার

• আকারের একটি অ্যারে অ্যারের সংজ্ঞা দিন:n.

• আরম্ভ করার জন্য i :=0, যখন i

  • arr[i] :=সংখ্যা[i] - x

• যোগফল :=0, শেষ :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • যোগফল :=যোগফল + arr[i]

• যদি যোগফল>=0 হয়, তাহলে −

  • প্রত্যাবর্তন সত্য

• আরম্ভ করার জন্য i :=0, j :=k, যখন j

  • last :=last + arr[i]

  • যোগফল :=যোগফল + arr[j]

  • যদি শেষ হয় <0, তাহলে −

    • যোগফল :=যোগফল - শেষ

    • শেষ :=0

  • যদি যোগফল>=0 হয়, তাহলে −

    • প্রত্যাবর্তন সত্য

• মিথ্যা ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ret :=0, low :=-inf, high :=inf

• যখন উচ্চ - নিম্ন> 10^-5, করুন

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

  • যদি ok(mid, nums, k) সত্য হয়, তাহলে −

    • নিম্ন :=মধ্য

    • ret :=মধ্য

  • অন্যথায়

    • উচ্চ :=মধ্য

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(double x, vector <int>& nums, int k){
      int n = nums.size();
      double arr[n];
      for (int i = 0; i < n; i++) {
         arr[i] = nums[i] - x;
      }
      double sum = 0;
      double last = 0;
      for (int i = 0; i < k; i++) {
         sum += arr[i];
      }
      if (sum >= 0)
      return true;
      for (int i = 0, j = k; j < n; i++, j++) {
         last += arr[i];
         sum += arr[j];
         if (last < 0) {
            sum -= last;
            last = 0;
         }
         if (sum >= 0)
         return true;
      }
      return false;
   }
   double findMaxAverage(vector<int>& nums, int k) {
      double ret = 0;
      double low = INT_MIN;
      double high = INT_MAX;
      while (high - low > 1e-5) {
         double mid = low + (high - low) / 2;
         if (ok(mid, nums, k)) {
            low = mid;
            ret = mid;
         } else {
            high = mid;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,12,-5,-6,50,3};
   cout << (ob.findMaxAverage(v, 4));
}

ইনপুট

{1,12,-5,-6,50,3},4

আউটপুট

12.75000