কোকো সি++ এ কলা খাচ্ছে

ধরুন আমাদের কলার N গাদা আছে, i-th পাইলে গাদা [i] কলা আছে। এখানে প্রহরীরা চলে গেছে এবং ঘন্টার মধ্যে ফিরে আসবে। কোকো তার কলা-প্রতি-ঘণ্টা খাওয়ার গতি নির্ধারণ করতে পারে। প্রতি ঘণ্টায়, সে কিছু গাদা কলা নেয় এবং সেই গাদা থেকে K কলা খায়। যদি স্তূপে K কলার কম থাকে, তাহলে সে তার পরিবর্তে সবগুলোই খেয়ে ফেলে এবং এই ঘণ্টায় আর কোনো কলা খাবে না। বিবেচনা করুন কোকো ধীরে ধীরে খেতে পছন্দ করে, কিন্তু তারপরও রক্ষীদের ফিরে আসার আগে সব কলা খাওয়া শেষ করতে চায়। আমাদের ন্যূনতম পূর্ণসংখ্যা K খুঁজে বের করতে হবে যাতে সে H ঘন্টার মধ্যে সব কলা খেতে পারে।

তাই যদি ইনপুট হয় [3,6,7,11], এবং H =8, তাহলে আউটপুট হবে 4।

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

ok() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি অ্যারে a, দুটি মান x এবং h
নেবে
সময় :=0
আমি 0 থেকে a
এর পরিসরে
- সময় :=সময় + a[i] / x
- সময় :=সময় + i যখন a[i] mod x হয় 0
যখন সময় <=H
সত্য ফেরত দিন
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
n :=পাইলস অ্যারের আকার, সমষ্টি সেট করুন :=0, নিম্ন :=1, উচ্চ :=0
0 থেকে n – 1
রেঞ্জের i জন্য
- উচ্চ :=পাইলসের সর্বোচ্চ [i] এবং উচ্চ
যখন কম <উচ্চ
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন) /2
- যদি ok(piles, mid, H) সত্য হয়, তাহলে উচ্চ সেট করুন :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 1
- যদি ok(piles, mid, H) সত্য হয়, তাহলে উচ্চ সেট করুন :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 1
উচ্চ রিটার্ন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   bool ok(vector <int>& a, int x, int H){
      int time = 0;
      for(int i = 0; i < a.size(); i++){
         time += a[i] / x;
         time += (a[i] % x ? 1 : 0);
      }
      return time <= H;
   }
   int minEatingSpeed(vector<int>& piles, int H) {
      int n = piles.size();
      lli low = 1;
      lli sum = 0;
      lli high = 0;
      for(int i = 0; i < n; i++)high = max((lli)piles[i], high);
      while(low < high){
         int mid = low + (high - low) / 2;
         if(ok(piles, mid, H)){
            high = mid;
         }else{
            low = mid + 1;
         }
      }
      return high;
   }
};
main(){
   vector<int> v = {3,6,7,11};
   Solution ob;
   cout << (ob.minEatingSpeed(v, 8));
}

ইনপুট

[3,6,7,11]
8