C++ में कोको ईटिंग केले

मान लीजिए कि हमारे पास केले के ढेर हैं, i-वें ढेर में ढेर [i] केले हैं। यहां गार्ड चले गए हैं और एच घंटे में वापस आ जाएंगे। कोको तय कर सकती है कि उसके प्रति घंटे केला खाने की गति K है। हर घंटे, वह केले का ढेर लेती है, और उस ढेर से K केले खाती है। यदि ढेर में K से कम केले हैं, तो वह इसके बजाय उन सभी का सेवन करती है, और इस घंटे के दौरान और केले नहीं खाएगी। गौर कीजिए कि कोको धीरे-धीरे खाना पसंद करता है, लेकिन फिर भी गार्ड के वापस आने से पहले सभी केले खाना चाहता है। हमें न्यूनतम पूर्णांक K ज्ञात करना है ताकि वह H घंटे के भीतर सभी केले खा सके।

तो अगर इनपुट [3,6,7,11] और एच =8 जैसा है, तो आउटपुट 4 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ओके () नामक एक विधि को परिभाषित करें, यह सरणी ए, दो मान x और h लेगा

• समय:=0

• मैं के लिए 0 से आकार के बीच में

  • समय :=समय + a[i] / x

  • समय:=समय + मैं जब एक [i] मॉड एक्स 0 है

• सही समय पर लौटें <=एच

• मुख्य विधि से निम्न कार्य करें

• n :=पाइल्स ऐरे का आकार, सेट योग :=0, निम्न :=1, उच्च :=0

• मेरे लिए 0 से n - 1 की सीमा में

  • उच्च :=अधिकतम बवासीर[i] और उच्च

• जबकि कम <उच्च

  • मध्य:=निम्न + (उच्च-निम्न) /2

  • यदि ठीक है (बवासीर, मध्य, एच) सत्य है, तो उच्च सेट करें:=मध्य, अन्यथा निम्न:=मध्य + 1

  • यदि ठीक है (बवासीर, मध्य, एच) सत्य है, तो उच्च सेट करें:=मध्य, अन्यथा निम्न:=मध्य + 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

आउटपुट

4