CSP-J 2022 第一轮 第 22 题：程序（二，鸡蛋掉落）：min函数执行次数是否为449次

题目

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         }
38     }
39
40     return h[n][m];
41 }
42
43 int main()
44 {
45     int n,m;
46     cin >> n>> m;
47     cout << f(n, m) << endl << g(n, m)<< endl;
48     return 0;
49 }

假设输入的n、m均是不超过100 的正整数，完成下面的判断题和单选题：

当输入为 7 3 时，第 $19$ 行用来取最小值的 min 函数执行了 $449$ 次。

选项

• A. 正确
• B. 错误

答案

B

题解

选 B，错误。第 19 行的 min 实际执行了 448 次。

设 \(T(n,m)\) 表示执行一次 f(n,m) 时，第 19 行 min 的总执行次数（包含所有递归调用）。

当 \(m=1\) 或 \(n=0\) 时，函数直接返回，不执行 min，因此： \[ T(n,1)=T(0,m)=0. \]

其他情况下，循环执行 \(n\) 次，每次包含：

• 当前这一层的 1 次 min；
• f(n-i,m) 内部的 min；
• f(i-1,m-1) 内部的 min。

注意，max 的两个参数都要计算，所以两次递归都要统计。于是： \[ T(n,m)=n+\sum_{i=1}^{n}\bigl[T(n-i,m)+T(i-1,m-1)\bigr]. \]

将 \(T(n,m)\) 和 \(T(n-1,m)\) 的表达式相减，可以得到更方便计算的递推式： \[ \boxed{T(n,m)=2T(n-1,m)+T(n-1,m-1)+1} \qquad(n\ge1,\ m\ge2). \]

据此填表：

最后一步为： \[ T(7,3)=2\times192+63+1=\boxed{448}. \]

这里已经包含最外层调用中的 min，不需要再加 1；g 中的 min 在第 34 行，也不计入本题。