题意
有一个 $N$ 层的大楼,你有 $M$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。
假设你在第 $x$ 层扔下鸡蛋,如果鸡蛋碎了,说明鸡蛋硬度不能承受在 $x$ 层扔下。如果没碎则说明鸡蛋硬度能承受在 $x$ 层扔下。
题解
动态规划解法
首先,我们可以看到网上的讨论,这是一道动态规划问题。
记 $f_{i, j}$ 表示用 $i$ 个鸡蛋测 $j$ 层高的楼的最少扔的次数。
首先,我们可以枚举一个 $k$,表示这次鸡蛋在第 $k$ 层扔。
那么就会有两种情况:
- 鸡蛋碎了,鸡蛋硬度在 $k$ 层以下,并且损失一个鸡蛋。所以 $f_{i, j} = 1 + f_{i - 1, k - 1}$。
- 鸡蛋没碎,鸡蛋硬度在 $k$ 层以上,并且没有损失鸡蛋。所以 $f_{i, j} = 1 + f_{i, j - k}$。
- 由于是求最坏情况,所以要取两者的最大值。而又由于我们可以决定在哪一层扔鸡蛋,所以我们在所有的 $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$ 个鸡蛋):
- 如果 $k \geq 5$,$x \geq \sum\limits_{i = 0}^n\sum\limits_{j = 0}^k\binom ij$
- 如果 $k = 2$,$x = \left \lceil \frac{\sqrt{8k + 1} - 1}2 \right \rceil$
- 如果 $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$
- 如果 $k = 4$,$x \geq \sum\limits_{i = 0}^n\left(\binom i4 + \binom i2\right)$
bykem · 2023-01-05 11:01
tql
yq 回复 bykem · 2023-03-03 20:26
%%%%%%
Orz012 · 2023-01-05 04:57
tql
Lightwhite · 2023-01-04 12:30
tql