Super Egg Drop trong C ++

Giả sử chúng ta đã cho K quả trứng và chúng ta có một tòa nhà có N tầng từ 1 đến N. Bây giờ, mỗi quả trứng đều giống hệt nhau về chức năng và nếu quả trứng bị vỡ, chúng ta không thể thả lại.

Tồn tại tầng F có từ 0 đến N sao cho bất kỳ quả trứng nào được thả ở tầng cao hơn tầng F sẽ bị vỡ và bất kỳ quả trứng nào được thả ở tầng F hoặc thấp hơn sẽ không bị vỡ. Trong mỗi lần di chuyển, chúng ta có thể lấy một quả trứng và thả nó từ bất kỳ tầng nào X. Dấu X nằm trong phạm vi từ 1 đến N.

Mục tiêu của chúng ta là biết chắc chắn giá trị của F là bao nhiêu. Vì vậy, số lần di chuyển tối thiểu mà chúng ta cần biết chắc chắn F là bao nhiêu, bất kể giá trị ban đầu của F là bao nhiêu?

Vì vậy, nếu đầu vào là K =2 và N =6, thì đầu ra sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một dp mảng 2D
Xác định một hàm giải quyết (), điều này sẽ nhận K, N,
nếu N <=1, thì -
- trả về N
nếu K giống với 1, thì -
- trả về N
nếu dp [K, N] không bằng -1 thì -
- trả về dp [K, N]
ret:=N, thấp:=0, cao:=N
- trong khi thấp <=cao, làm -
- left:=1 + giải quyết (K - 1, giữa - 1)
- phải:=1 + giải quyết (K, N - giữa)
- ret:=tối thiểu ret và tối đa trái và phải
- nếu bên trái giống bên phải, thì -
  - Ra khỏi vòng lặp
- nếu trái
  - thấp:=mid + 1
- nếu không thì cao:=mid - 1
return dp [K, N] =ret
Frm phương thức chính thực hiện như sau -
dp:=Tạo một mảng 2D (K + 1) x (N + 1), điền vào giá trị này bằng -1
trả về giải quyết (K, N)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

2, 6

Super Egg Drop trong C ++

Ví dụ

Đầu vào

Đầu ra