深入探究大楼丢鸡蛋问题（胡扯版）

这篇博客已过时

最新版

题意

有一个 $N$ 层的大楼，你有 $M$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。
假设你在第 $x$ 层扔下鸡蛋，如果鸡蛋碎了，说明鸡蛋硬度不能承受在 $x$ 层扔下。如果没碎则说明鸡蛋硬度能承受在 $x$ 层扔下。

题解

动态规划解法

首先，我们可以看到网上的讨论，这是一道动态规划问题。
记 $f_{i, j}$ 表示用 $i$ 个鸡蛋测 $j$ 层高的楼的最少扔的次数。
首先，我们可以枚举一个 $k$，表示这次鸡蛋在第 $k$ 层扔。
那么就会有两种情况：

1. 鸡蛋碎了，鸡蛋硬度在 $k$ 层以下，并且损失一个鸡蛋。所以 $f_{i, j} = 1 + f_{i - 1, k - 1}$。
2. 鸡蛋没碎，鸡蛋硬度在 $k$ 层以上，并且没有损失鸡蛋。所以 $f_{i, j} = 1 + f_{i, j - k}$。
3. 由于是求最坏情况，所以要取两者的最大值。而又由于我们可以决定在哪一层扔鸡蛋，所以我们在所有的 $k$ 中取最小值。 于是式子就是这样：
   $$f_{i, j} = \min\limits_{i = 1}^j\max\left{f_{i - 1, k - 1}, f_{i,
   j - k}\right}$$

然后我们发现复杂度有点高，尝试优化。
其实我们发现，随着 $k$ 的增加，$f_{i - 1, k - 1}$ 单调不减，$f_{i, j - k}$ 单调不增。所以 $\max\left\{f_{i - 1, k - 1}, f_{i, j - k}\right\}$ 的最小值在两函数交点处。所以我们可以二分求出这个交点。
此时复杂度降至 $\mathcal O\left(MN \log n\right)$

/*
 * Please submit with C++14! It's best to use C++20 or higher version.
 * By rbtree (https://rbtr.ee)
 * Apparition (n@rbtr.ee)
 * DO OR DIE
 */

#include <cmath>
#include <cstdio>
#include <cstring>
#define AS 3 +

using namespace std;
using tp = long long;

constexpr tp Hat_M = 30, Hat_N = 1e5;

tp f[AS Hat_M][AS Hat_N];

signed main() {
  tp m, n;
  scanf("%lld%lld", &m, &n);
  memset(f, 0x3f, sizeof f);
  for (tp i = 0; i < Hat_N; ++i) f[1][i] = i;
  for (tp i = 0; i < Hat_M; ++i) f[i][0] = 0;
  for (tp i = 0; i < Hat_M; ++i) f[i][1] = 1;
  for (tp i = 2; i <= m; ++i) {
    for (tp j = 2; j <= n; ++j) {
      tp l = 1, r = j;
      while (l <= r) {
        tp mid = l + r >> 1, a = f[i - 1][mid - 1], b = f[i][j - mid];
        if (a > b) r = mid - 1;
        else l = mid + 1;
      }
      f[i][j] = min(f[i][j], max(f[i - 1][r - 1], f[i][j - r]) + 1);
    }
  }
  printf("%lld\n", f[m][n]);
  return 0;
}

//*/

推通项解法

我们先求出 $M = 2$ 时的通解，再求出 $M = 3$ 时的通解，先找找规律。

M	N	结果
2	1	1
2	100	14
2	10000	141
2	1000000	1414
2	100000000	14142

发现了吗？$f_{2, n}$ 居然等于 $\sqrt{2 \cdot n}$！接下来我们求 $M = 3$ 时的通解。

M	N	结果
3	1000	19
3	1000000	182
3	1000000000	1818

这次的规律没那么明显了，肉眼不可见。于是我就到 wolframalpha 上查了一下，$\sqrt[3]6 \approx 1.8171205928321396588$，与上面的表这个十分接近，但又不完全一致。所以这时可以发现
，其实在 $M = 2$ 时 $f_{2, n}$ 可能也只是接近 $\sqrt{2 \times n}$。

所以 $M = 3$ 时，$f_{3, n}$ 近似等于 $\sqrt[3]{6 \cdot n}$

目前肉眼看不出什么规律来。所以再求 $M = 4$ 时的通解。

M	N	结果
3	10000	23
3	100000000	222
3	1000000000000	2214
3	10000000000000000	22135

这下完了，wolframalpha 上也查不到关于 2.2135 的信息。但是我突然发现，$M = 2$ 时这个常数是开 $2$ 次根，$M = 3$ 时这个常数是开 $3$ 次根，那 $M = 4$ 时是不是要开 $4$ 次根了？所以把 2.2135 四次方，得到 $24.00590622$，非常接近 $24$。
所以现在 $M = 4$ 时的解也求出来了：$f_{4, n}$ 近似等于 $\sqrt[4]{24 \cdot n}$。

这下可以看出规律了吧。这个常数等于 $\sqrt[M]{M!}$。

所以 $f_{m, n}$ 近似等于 $\sqrt[M]{NM!}$。

用这个公式验证了几个 $M$ 较大的情况，发现确实很接近，但还是有一些误差。

动脑子推通项解法

怎么个丢法是最优的呢？考虑 $2$ 个蛋的情况下，扔 $x$ 次最多能检测多少层楼。
第一次扔的时候：
如果碎了，那么接下来就要一层一层试，要扔 $x - 1$ 次
如果没碎，就变成了次数为 $x - 1$ 的子问题了，此时再扔的楼层数变成了 $2x - 1$，在这种情况下碎和不碎两种情况下需要再扔的次数是相等的，已经是最好的扔法了，继续，可以得到，扔 $x$ 次时，最高可以检测到的楼层数为：
$$\sum\limits_{i = 1}^x i = \frac{x(1 + x)}2$$
那如果要检测 $100$ 层楼，又 $\frac{x(1 + x)}2 \geq 100$，解得 $x = 14$，是对的。
所以解得，两个蛋，$k$ 层楼时，最优的丢鸡蛋次数是
$$x = \left \lceil \frac{\sqrt{8k + 1} - 1}2 \right \rceil$$

接下来考虑 $3$ 个蛋的情况，同样的方法，发现扔 $x$ 次时，最高可以检测到的楼层数为：
$$\frac{x^3 + 5x}6$$
所以解得，三个蛋，$k$ 层楼时，最优的丢鸡蛋次数是
$$\large x = \left \lceil \frac{\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}}{3^{\frac23}} - \dfrac5{\sqrt[3]3\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}} \right \rceil$$
（放心，没写错）

接下来考虑 $4$ 个蛋的情况，用同样的方法可以推出。
为了方便接下来推式子，我们把“扔 $n$ 次时，最高可以检测到的楼层数”写成组合数的形式：
两个蛋：$\binom{n + 1}2$
三个蛋：$\binom n1 + \binom n2 + \binom n3$
四个蛋：$\binom n4 + \binom n2$

从 OEIS 上搜到的数列的解释是：由 $n - 1$ 个超平面形成的 $k$ 维空间中的区域数。
也就是说，有 n 层楼，k 个鸡蛋，答案将是 由 $n - 1$ 个超平面形成的 $k$ 维空间中的区域数。

形式化的，通解是（$n$ 层楼，$k$ 个鸡蛋）：

1. 如果 $k \geq 5$，$x \geq \sum\limits_{i = 0}^n\sum\limits_{j = 0}^k\binom ij$
2. 如果 $k = 2$，$x = \left \lceil \frac{\sqrt{8k + 1} - 1}2 \right \rceil$
3. 如果 $k = 3$，$\large x = \left \lceil \frac{\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}}{3^{\frac23}} - \dfrac5{\sqrt[3]3\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}} \right \rceil$
4. 如果 $k = 4$，$x \geq \sum\limits_{i = 0}^n\left(\binom i4 + \binom i2\right)$

---

• 分类： 做题笔记
• 最后更新于：2024-04-28 21:04:32^UTC+8
• 标签： 动态规划 思维 动态规划优化 数学