CSP-J 入门级 · CSP 2022 入门级第一轮 第 17 题

（2）

1  #include <algorithm>
2  #include <iostream>
3  #include <limits>
4  
5  using namespace std;
6  
7  const int MAXN = 105;
8  const int MAXK = 105;
9  
10 int h[MAXN][MAXK];
11 
12 int f(int n, int m)
13 {
14     if (m == 1) return n;
15     if (n == 0) return 0;
16 
17     int ret = numeric_limits<int>::max();
18     for (int i = 1; i <= n; i++)
19         ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
20     return ret;
21 }
22 
23 int g(int n, int m)
24 {
25     for (int i = 1;i <= n; i++)
26         h[i][1]= i;
27     for (int j = 1;j<= m; j++)
28         h[0][j]= 0;
29 
30     for (int i= 1; i <= n; i++){
31         for (int j= 2; j <= m; j++){
32             h[i][j] = numeric_limits<int>::max();
33             for (int k = 1;k <= i;k++)
34             h[i][j]= min(
35                 h[i][j],
36                 max(h[i - k][j],h[k - 1][j - 1]) +1);
37         }

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题是经典的“鸡蛋掉落”问题，核心在于理解 f(n,m) 和 g(n,m) 都是求最坏情况下的最少尝试次数。拿到题先别急着套公式，要抓住转移方程背后的物理意义：在第 i 层扔，碎了往下缩，没碎往上缩，取两种路径的最大值再加一。

最容易错的是把 min 函数的执行次数数错。很多人看到三重循环就以为要算 i*k 次，却忘了循环的终止条件 k<=i，导致把 7*3 的简单乘积当成答案，或者把 min 调用的总次数算成 (n-1)*(m-1) 的某种变体。其实 min 被调用的次数等于所有合法分割点 i 的数量乘以所有合法 k 的数量，也就是 n*(n+1)/2 * m，代入 n=7,m=3 得到 28*3=84，远非 449。另一个坑是误以为两函数结果不同，其实它们只是自顶向下和自底向上的写法差异，逻辑完全一致。还有人对 m=1 的情况理解不深，以为可以二分，其实只有一个鸡蛋时只能线性扫描，必须试 n 次。

这道题考查的是动态规划中的“鸡蛋掉落”问题，属于 CSP-J/S 入门级常见题型，也是历年 GESP 和 NOIP 普及组反复出现的考点。命题人喜欢用这道题检验学生是否真正理解 DP 转移的构造过程，而不仅仅是背公式。它同时考察了递归与迭代两种实现方式，以及时间复杂度的分析能力。

我们先来拆解题目给的代码。f(n,m) 是递归版本，g(n,m) 是填表版本。两者的核心思想完全相同：给定 n 层楼和 m 个鸡蛋，求在最坏情况下最少需要试多少次才能确定安全楼层。状态定义很直观：f(n,m) 表示 n 层楼 m 个鸡蛋的最优解。

转移方程怎么来的？我们考虑在第 i 层扔鸡蛋（1≤i≤n）。这里有两个分支： 1. 鸡蛋碎了：说明安全楼层在 i 层以下，剩下 i-1 层，鸡蛋只剩 m-1 个，代价是 f(i-1, m-1)； 2. 鸡蛋没碎：说明安全楼层在 i 层以上，剩下 n-i 层，鸡蛋还是 m 个，代价是 f(n-i, m)。 因为我们要考虑最坏情况，所以这次操作带来的代价是 max(f(i-1, m-1), f(n-i, m))。再加上本次尝试本身，就是 max(...) + 1。 我们在所有可能的 i 中取最小值，得到： f(n, m) = min_{1≤i≤n} { max(f(i-1, m-1), f(n-i, m)) + 1 } 边界条件也很自然：如果只有一个鸡蛋（m=1），只能从一楼开始逐层试，试 n 次；如果楼层为 0，不需要试。

g(n,m) 就是把上面的递归改成自底向上的 DP。它先初始化 h[i][1]=i（一个鸡蛋的情况），再按列枚举鸡蛋数 j，按行枚举楼层数 i，内层枚举分割点 k。注意这里的 k 对应递归里的 i，所以内层循环 k 从 1 到 i，计算 h[i][j] = min(h[i][j], max(h[i-k][j], h[k-1][j-1]) + 1)。这个三重循环结构非常清晰，也方便我们分析复杂度。

现在逐题分析。

第一小题：当输入为 7 3 时，第 19 行用来取最小值的 min 函数执行了多少次？ 第 19 行是：ret = min(ret, max(f(n-i, m), f(i-1, m-1)) + 1); 这里的 min 被调用的次数等于外层循环 i 从 1 到 n 执行的次数，乘以每次循环中 min 被调用 1 次。也就是说，对于固定的 n 和 m，min 被调用的总次数就是 n 次（因为每次 i 对应一次 min 调用）。但是题目问的是“第 19 行用来取最小值的 min 函数执行了 449 次”，这显然不对。我们再看代码：在 f 函数中，min 只出现在第 19 行，每次循环调用一次。当 n=7 时，i 从 1 到 7，min 被调用 7 次。等等，这里有个误解：实际上，min 函数在每次循环中被调用一次，但 ret 的初始值是 INT_MAX，然后不断更新。所以 min 被调用的次数就是 n 次。但题目说的是 449 次，这明显是错误的。我们再仔细检查：在 g 函数中，min 出现在第 34-36 行，那里有一个三重循环：i 从 1 到 n，j 从 2 到 m，k 从 1 到 i。min 被调用的次数是 sum_{i=1}^{n} sum_{j=2}^{m} i = m-1 * n*(n+1)/2。当 n=7,m=3 时，次数 = 2 * 7*8/2 = 56。也不等于 449。所以无论在哪一行，449 都是错的。正确答案是 B。

第二小题：输出的两行整数总是相同的。 因为 f 和 g 计算的是同一个 DP 状态，只是实现方式不同（递归 vs 迭代），它们的结果必然一致。无论输入 n,m 是多少，f(n,m) 和 g(n,m) 都返回相同的值。所以输出两行整数总是相同，正确，选 A。

第三小题：当 m 为 1 时，输出的第一行总为 n。 当 m=1 时，f(n,1) 直接返回 n，g(n,1) 也通过初始化 h[i][1]=i 得到 n。所以输出第一行确实是 n，正确，选 A。

第四小题：算法 g(n,m) 的时间复杂度。 g 函数有三重循环：外层 i 从 1 到 n，中层 j 从 2 到 m，内层 k 从 1 到 i。min 被调用的次数是 sum_{i=1}^{n} sum_{j=2}^{m} i = (m-1) * n*(n+1)/2 = O(n²m)。所以最准确的复杂度是 O(n²m)，选 C。

第五小题：输入 20 2 时，输出第一行是多少？ 这是经典的“2 个鸡蛋”问题。我们可以手算或用 DP 验证。f(20,2) 的转移是 min_{i=1}^{20} max(f(i-1,1), f(20-i,2)) + 1。由于 f(x,1)=x，所以 max(x, f(20-i,2)) 在 i 较小时由 x 主导，i 较大时由 f(20-i,2) 主导。这个 DP 的值是 6。也可以从数学角度理解：2 个鸡蛋时，最优策略是第一次在 x 层扔，如果碎了，剩下 x-1 层用 1 个鸡蛋线性试；如果没碎，剩下 20-x 层用 2 个鸡蛋。平衡两者得到 x≈6。所以答案是 6，选 C。

第六小题：输入 100 100 时，输出第一行是多少？ 当鸡蛋数量足够多（m≥log₂n）时，我们可以用二分策略，每次把搜索区间减半，最坏情况需要 ⌈log₂n⌉ 次。对于 n=100，log₂100≈6.64，向上取整是 7。DP 也会给出同样的结果，因为当 m 很大时，max(f(i-1,m-1), f(n-i,m)) 在 i≈n/2 时最小。所以答案是 7，选 B。

总结一下，这道题的关键在于理解 DP 转移的构造过程，以及区分递归和迭代实现的本质相同。命题人喜欢在这里挖坑，比如让学生误以为 min 调用次数是 n*(n+1)/2 或类似错误值，或者让学生混淆鸡蛋数量对策略的影响。记住：一个鸡蛋只能线性试，两个鸡蛋可以用“第一次在 x 层扔”的策略，鸡蛋更多时接近二分。掌握这些，就能轻松应对这类题目。