解题思路

给定 k 枚鸡蛋与 n 层楼，问在最坏情况下确定临界层所需的最小操作次数。经典做法是将“最少次数”换个角度建模为“在给定操作次数内最多能确定的楼层数”。

相关算法：动态规划（DP，按操作次数推进）。

核心思路（按“操作次数 m”推进的 DP）：

• 设 dp[m][e] 表示在最多操作 m 次、手里有 e 枚鸡蛋时，最多能确定的楼层数量。

• 第 m 次在某层扔鸡蛋：

  • 若碎了：还剩 e-1 枚、还能操作 m-1 次，可覆盖 dp[m-1][e-1] 层（在下面）。
  • 若没碎：鸡蛋仍有 e 枚、还能操作 m-1 次，可覆盖 dp[m-1][e] 层（在上面）。

• 再加上当前这一层，因此有递推式：

  dp[m][e] = dp[m-1][e-1] + dp[m-1][e] + 1
  

• 从 m=1 开始递增，计算到某个最小 m 使得 dp[m][k] ≥ n，该 m 即答案。

实现要点：

• 由于 dp[m][e] 仅依赖 m-1 行，可用一维数组从高到低更新 e，空间优化到 O(k)。
• 与“按楼层数枚举”的传统 DP 相比，本解法无需二分或三角不等式，写法简洁、效率高。

复杂度分析

• 时间复杂度：O(k · m)，其中 m 为答案（最少操作次数）。在实际数据范围内，m 约为 O(log n) 到 O(√n) 之间，远小于 n，复杂度可接受。
• 空间复杂度：O(k)，使用一维数组保存当前 dp[*]。

代码实现

Python

# 参考题面给出的 Python 模板
import sys

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # dp[e] 表示在当前操作次数 m 下、手里有 e 枚鸡蛋时最多能确定的楼层数
        dp = [0] * (k + 1)
        m = 0
        # 不断增加操作次数，直到覆盖的楼层数 >= n
        while dp[k] < n:
            m += 1
            # e 必须从大到小更新，避免本轮结果污染上一轮
            for e in range(k, 0, -1):
                dp[e] = dp[e] + dp[e - 1] + 1
        return m

def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    data = data.replace(",", " ")
    nums = [int(x) for x in data.split()]
    if len(nums) < 2:
        return
    k, n = nums[0], nums[1]
    print(Solution().superEggDrop(k, n))

if __name__ == "__main__":
    main()

Java

class Solution {
    public int superEggDrop(int k, int n) {
        // dp[e]：在当前操作次数 m 下、e 枚鸡蛋能覆盖的最大楼层数
        long[] dp = new long[k + 1];
        int m = 0;
        while (dp[k] < n) {
            m++;
            for (int e = k; e >= 1; e--) {
                dp[e] = dp[e] + dp[e - 1] + 1;
            }
        }
        return m;
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && Character.isWhitespace(c));
            if (c == -1) return null;
            do {
                char ch = (char) c;
                if (ch == ',') ch = ' '; // 支持逗号分隔
                sb.append(ch);
                c = read();
            } while (c != -1 && !Character.isWhitespace(c));
            return sb.toString().trim();
        }
        Integer nextInt() throws IOException {
            String s = next();
            return s == null ? null : Integer.parseInt(s);
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        Integer k = fs.nextInt();
        Integer n = fs.nextInt();
        if (k == null || n == null) return;
        Solution sol = new Solution();
        System.out.println(sol.superEggDrop(k, n));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<long long> dp(k + 1, 0); // dp[e]：当前操作次数下可覆盖楼层
        int m = 0;
        while (dp[k] < n) {
            m++;
            for (int e = k; e >= 1; --e) {
                dp[e] = dp[e] + dp[e - 1] + 1;
            }
        }
        return m;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读取整行并兼容逗号/空格分隔
    string all;
    {
        ostringstream oss;
        string line;
        while (getline(cin, line)) {
            oss << line << ' ';
        }
        all = oss.str();
    }
    for (char& c : all) if (c == ',') c = ' ';
    istringstream iss(all);
    int k, n;
    if (!(iss >> k >> n)) return 0;

    Solution sol;
    cout << sol.superEggDrop(k, n) << "\n";
    return 0;
}

题目描述

给你 k 枚相同的鸡蛋，以及一栋从第 1 层到第 n 层共有 n 层的建筑。存在某一楼层 f（0 ≤ f ≤ n），使得：

• 从高于 f 的楼层扔下鸡蛋一定会碎；
• 从 f 楼层或更低楼层扔下鸡蛋不会碎。

每次操作可选择任一未碎鸡蛋，从任一楼层 x（1 ≤ x ≤ n）扔下。若鸡蛋碎则不可再用；若没碎可再次使用。请计算确定 f 的确切值所需的最少操作次数（最坏情况）。

输入格式

• 一行，包含两个整数 k 和 n，表示鸡蛋数量与楼层数。 （可接受用空格或逗号分隔，如 3 14 或 3,14）

输出格式

• 输出一个整数，表示最少操作次数。

样例1

输入

1 2

输出

2

样例2

输入

2 6

输出

3

样例3

输入

3 14

输出

4