高空坠物

前几天在我校OJ上看到这样的一道题:

[109 高楼坠物实验]METO 手中有若干个硬度一样的篮球。这天,他发现一个测试篮球硬度的好方法:从高楼的某一层 $x$ 上把篮球扔下去,如果篮球爆了,代表它的硬度小于 $x$;反之硬度则大于等于 $x$。显然可以找到某一层楼 $X$,使得从 $X$ 及以下的楼层扔下篮球而不爆掉,从 $X+1$ 及以上的楼层扔下会爆掉。那么篮球的硬度就为 $X$。
METO 找到了一栋 $N$ 层楼高的大厦来进行测试,已知 METO 手里有 $K$ 个篮球,那么在最坏情况下至少需要多少次才能测试出篮球的硬度。(篮球一旦爆掉就不能进行测量,存在在第 $1$ 层扔下就炸掉或者第 $N$ 层扔下也不爆的情况)

瞎读了一通题面感觉似乎就是二分搞?乱敲一通过了样例果然就WA了……
仔细想想题目要求的“最坏情形”是怎样的一回事呢?我们不难发现,对于只有$1$个球的情形,只能一层一层往上尝试,最坏的情形就是楼的层数;那么对于$2$个球的情形该怎么处理呢?
朴素的想法是,尽可能地发挥第$1$个球的作用:即如果在某一层楼$k$的时候球碎了,那么我们希望这个$k$尽可能的小;如果在$k$层没有碎,那么我们希望我们的测试次数尽可能的少.
也就是说,如果我们设最后的答案是$f(n)$,$n$代表楼的层数,第一次选择在$k$层楼扔下球,那么我们有:
$$f(n)=1+max(f(n-k),f(k-1))$$
其中,$f(n-k)$和$f(k-1)$分别对应在第$k$层没有碎和碎掉的情形.
这似乎在暗示这道题是DP?考虑下有$m$个球的情形:
我们设楼的层数为$n$,一共有$m$个球.类比刚才的思路,如果我们选择在第$k$层扔下球:

情形一 球没炸

这好办,我们现在手里还有 $m$ 个球,楼的规模变小了,答案也就是$f[n-k][m] + 1$.

情形二 球炸了

我们手里剩下了$m-1$个球,楼的规模变成了$k-1$.答案为$f[k-1][m-1] + 1$.
似乎没有其他的情形了?题目要求我们求最后的最坏情况的最小值,那么我们应该得到这样的DP:
$$f[n][m]=min(f[n][m],max(f[n-k][m],f[k-1][m-1]) + 1)$$
那么边界怎么搞呀?$1$个球的情形时显然答案为$f[n][1] = n$,$m$个球的时候最坏的情形肯定是这些球的硬度都超过了$n$.所以最初的状态应该设置成$f[n][m] = n$,复杂度为$O(N*M^2)$

#include <bits/stdc++.h>
using namespace std;
int f[1005][55]{0};
int main(void) {
    int n = 1001, w = 51;
    for (int i = 1; i <= n; ++i) f[i][1] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= w; ++j) {
            f[i][j] = i;
            for (int k = 1; k < i; ++k) 
                f[i][j] = min(f[i][j], max(f[i - k][j], f[k - 1][j - 1]) + 1);
        }
    while (cin >> n >> w)
        printf("%d\n", f[n][w]);
    return 0;
}

更进一步

然而这道题的复杂度还可以再优化.我们可以设$k$个球在$m$步内能够测量出来的最大楼层数.最后我们的答案变为,寻找当$k\leq K$时的最小的$m$使得$f[k][m]\leq N$
首先考虑只有$1$只球的情形:
$$f[1][m] = m$$
这是显然的,因为最坏情形时球的硬度是要超过$n$的.
那么类比刚才的做法,考虑第$m$步时:
$$f[k][m] = f[k-1][m-1] + f[k][m-1] + 1$$
其中$f[k-1][m-1]$是球碎的情形,$f[k][m-1]$为球没碎的情形,1是当前楼层,所以方案数加一.
值得一提的是,我们在求方案数的时候,并不关心具体楼层的高度(或者球的硬度),我们关心的是当前楼的规模(总大小).
这有点像是求背包的方案数.

    //m是球的个数,n是楼的层数
    for (int i = 1; i <= n; ++i) f[1][i] = i;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            f[j][i] = f[j][i - 1] + f[j - 1][i - 1] + 1;
            if (f[j][i] >= n); /*i是答案*/
        }
    }
    //否则答案是n

实际上这道题来自于(Leetcode-887)扔鸡蛋,这道题只是把题面稍微改动了一下.
另外,我们不仅可以扔篮球、扔鸡蛋,还可以(UVA-10934)扔水球

参考

  1. Leetcode 887 Super Egg Drop(扔鸡蛋) DP
此条目发表在未分类分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注