C ++中的超级鸡蛋滴

假设我们给了K个鸡蛋,并且我们有一个N层从1到N的建筑物。现在每个鸡蛋的功能是相同的,并且如果一个鸡蛋破裂了,我们就不能再次丢弃它。

存在一个介于0到N之间的F层,这样,落在F层以上的任何鸡蛋都不会破裂,而落在F层以下或F层以下的任何鸡蛋都不会破裂。在每一步中,我们可能会拿一个鸡蛋并将其从任意楼层X放下。X的范围是1到N。

我们的目标是确定F的值。那么,无论F的初始值如何,我们需要确定地知道F是多少的最小移动次数是多少?

因此,如果输入为K = 2且N = 6,则输出为3。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个2D数组dp

  • 定义一个函数solve(),它将取K,N,

  • 如果N <= 1,则-

    • 返回N

  • 如果K等于1,则-

    • 返回N

  • 如果dp [K,N]不等于-1,则-

    • 返回dp [K,N]

  • ret:= N,低:= 0,高:= N

    • 低:=中+ 1

    • 从循环中出来

    • 当低<=高时,执行-

    • 左:= 1 +求解(K-1,中-1)

    • 右:= 1 + Solve(K,N-mid)

    • ret:= ret的最小值和left和right的最大值

    • 如果左与右相同,则-

    • 如果左<右,则:

    • 否则高:=中-1

    • 返回dp [K,N] = ret

    • Frm主要方法执行以下操作-

    • dp:=创建一个2D数组(K + 1)x(N +1),并用-1填充

    • 返回求解(K,N)

    让我们看下面的实现以更好地理解-

    示例

    #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