C++ में सुपर एग ड्रॉप

मान लीजिए हमने K अंडे दिए हैं, और हमारे पास 1 से N तक N मंजिलों वाली एक इमारत है। अब प्रत्येक अंडा कार्य में समान है, और यदि कोई अंडा टूटता है, तो हम उसे दोबारा नहीं गिरा सकते।

0 और N के बीच एक मंजिल F मौजूद है, ताकि F से ऊंची मंजिल पर गिरा कोई भी अंडा टूट जाए, और मंजिल F पर या नीचे गिरा हुआ कोई भी अंडा नहीं टूटेगा। प्रत्येक चाल में, हम एक अंडा ले सकते हैं और उसे किसी भी मंजिल X से गिरा सकते हैं। X 1 से N की सीमा में है।

हमारा लक्ष्य निश्चित रूप से यह जानना है कि F का मान क्या है। तो, चालों की न्यूनतम संख्या क्या होगी जो हमें निश्चित रूप से जानने के लिए आवश्यक है कि F क्या है, F के प्रारंभिक मान की परवाह किए बिना?

इसलिए, यदि इनपुट K =2 और N =6 जैसा है, तो आउटपुट 3 होगा।

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

• एक 2डी सरणी डीपी परिभाषित करें

• एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें K, N,

  लगेगा

• अगर एन <=1, तो -

  • वापसी एन

• यदि K 1 के समान है, तो -

  • वापसी एन

• अगर dp[K, N] -1 के बराबर नहीं है, तो -

  • वापसी डीपी [के, एन]

• रिट:=एन, लो:=0, हाई:=एन

  • जबकि कम <=उच्च, करें −

  • बाएँ :=1 + हल करें(K-1, मध्य -1)

  • दाएं:=1 + हल करें (के, एन - मध्य)

  • ret :=न्यूनतम रिट और अधिकतम बाएँ और दाएँ

  • यदि बायाँ दाएँ के समान है, तो -

    • लूप से बाहर आएं

  • अगर बाएं <दाएं, तो:

    • कम :=मध्य + 1

  • अन्यथा उच्च :=मध्य - 1

• वापसी डीपी [के, एन] =सेवानिवृत्त

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

• dp :=एक 2D सरणी बनाएं (K + 1) x (N + 1), इसे -1 से भरें

• वापसी हल (के, एन)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int>> dp;
   int solve(int K, int N) {
      if (N <= 1)
         return N;
      if (K == 1)
         return N;
      if (dp[K][N] != -1)
         return dp[K][N];
      int ret = N;
      int low = 0;
      int high = N;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         int left = 1 + solve(K - 1, mid - 1);
         int right = 1 + solve(K, N - mid);
         ret = min(ret, max(left, right));
         if (left == right)
         break;
         if (left < right) {
            low = mid + 1;
         } else
            high = mid - 1;
      }
      return dp[K][N] = ret;
   }
   int superEggDrop(int K, int N) {
      dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
      return solve(K, N);
   }
};
main(){
   Solution ob;
   cout << (ob.superEggDrop(2,6));
}

इनपुट

2, 6

आउटपुट

3