17蓝桥杯题解——摔手机

3-范天祚
3-范天祚   发布于 2018-12-13 12:18
阅读量: 347

原文链接:博客原文

原文阅读体验更好,大家去支持一下吧。。

 

今天有人提醒我记得报名蓝桥杯,300块钱挺贵的,不太像报,因为拿了奖并不能证明自己很厉害,没拿奖反而证明自己很菜。。。太亏了。

 

但是里面一些题还是不错的,所以有空就写一下题解。

今天是一道动态规划,可以借此题打开一定的思路。

 

早就想写这个题的题解,竟然已经拖了半年之久了。今天想起来,一定要写出来。

 

原题描述:


        x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
        x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
        如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。

特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n

        为了减少测试次数,从每个厂家抽样3部手机参加测试。
        某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
        请填写这个最多测试次数。

        注意:需要填写的是一个整数,不要填写任何多余内容

答案19

 

文章目的
 

读完题后,我们追求的不是要写出得数(至少对于本博客是不够的),而是用代码实现方法,并思考是否可以优化。

其实本题的方法是非常多种多样的。非常适合锻炼思维。

我们把问题扩展到n个手机来思考。

手机k个,楼n层,最终结果M次。

时空复杂度目录
暴力:                        O(N!)

DP:                            O(N*N*K)  O(N*K)

压空间:                    O(N*N*K)  O(N)

四边形不等式优化     O(N*N)       

换思路:                    O(K*M)

最优:                         O(K*M)    O(N)

文末有测试,大家可以去直观感受一下各方法运行的效率

二分
 

容易想到二分思路:不断二分范围,取中点,测验是否会摔坏,然后缩小一半范围,继续尝试,很显然,答案为logN(2为底)

但是,二分得出的答案是不对的。注意:我们要保证在都手机摔完之前,能确定耐摔指数到底是多少。

举例:

我们在500楼摔坏了,在250楼摔,又坏了。接下来,我们只能从1楼开始一层一层试

因为如果我们在125层摔坏了,就没有手机可以用,也就是永远都测不出来,而这是不被允许的。其实我们连测第2层都不敢测,因为在第2层摔坏了,我们就无法知道手机在第一层能否被摔坏。所以只有一部手机时,我们只敢从第一层开始摔。

 

尝试较优的策略
 

既然二分是不对的,我们继续分析:摔手机的最优策略到底是如何的。

只有一部手机时,我们只敢从第一层开始摔。

有两部手机的时候,我们就敢隔层摔了,因为一部手机坏了,我们还有另一部来继续试。

这时就有点意思了,我们分析情况:

情况1)假设我们第一部手机在i层摔坏了,然后最坏情况还要试多少次?这时我们还剩一部手机,所以只敢一层一层试,最坏情况要试到i-1层,共试了i次。

情况2)假设我们第一部手机在i层试了,但是没摔坏,然后最坏情况还要试多少次?(这时发现算情况2时依旧是相似的问题,确定了可以用递归来解。)

 

最优解(最小值)是决策后两种情况的最差情况(最大值),我们的本能感觉应该就是让最差情况好一点,让最好情况差一点,这样比较接近正确答案。比如两部手机,一百层,我们可以在50层摔,没坏,这一次就很赚,我们没摔坏手机还把范围缩小了50层。如果坏了,就比较坑了,我们要从1试到50。虽然可能缩小一半,但是最坏情况次数太多,所以肯定要从某个低于五十的层开始尝试。

(以上几行是为了让读者理解决策,下面正文分析)

 

归纳表达式
 

假设我们的楼一共n层,我们的i可以取1-n任意值,有很多种可能的决策,我们的最小值设为f(n,k),n代表楼高(范围为1-100或101-200其实都一样),k代表手机数.

我们假设的决策是在第i楼扔

对于情况一,手机少了一部,并且我们确定了范围,一定在第i楼以下,所以手机-1,层数为i-1,这时f(n,k)=f(i-1,k-1).

对于情况二,手机没少,并且我们确定了范围,一定在第i楼之上,所以手机数不变,而层数-i层,这时f(n,k)=f(n-i,k).

归纳出

f(n,k)=min(  max(f(i-1,k-1) ,f(n-i,k) ) i取1-n任意数    )

简单总结:怎么确定第一个手机在哪扔?每层都试试,哪层的最坏情况(max)最好(min),就去哪层扔。

 

写出暴力递归


按照分析出来的表达式,我们可以写出暴力递归:

    public static int solution1(int nLevel, int kChess) {
        if (nLevel == 0) {
            return 0;
        }//范围缩小至0
        if (kChess == 1) {
            return nLevel;
        }//每层依次试
        int min = Integer.MAX_VALUE;//取不影响结果的数
        for (int i = 1; i != nLevel + 1; i++) {
                      //尝试所有决策,取最优
            min = Math.min(
                    min,
                    Math.max(Process1(i - 1, kChess - 1),Process1(nLevel - i, kChess)));
        }
        return min + 1;//别忘了加上本次
    }
 

改为动态规划
 

具体思路如下

具体思路讲解

 

    public static int solution2(int nLevel, int kChess) {
        if (kChess == 1) {
            return nLevel;
        }
        int[][] dp = new int[nLevel + 1][kChess + 1];
        for (int i = 1; i != dp.length; i++) {
            dp[i][1] = i;
        }
        for (int i = 1; i != dp.length; i++) {
            for (int j = 2; j != dp[0].length; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 1; k != i + 1; k++) {
                    min = Math.min(min,
                            Math.max(dp[k - 1][j - 1], dp[i - k][j]));
                }
                dp[i][j] = min + 1;
            }
        }
        return dp[nLevel][kChess];
    }
 

压缩空间
 

我们发现,对于状态转移方程,只和上一盘排的dp表和左边的dp表有关,所以我们不需要把值全部记录,用两个长度为n的数组不断更新即可(具体对dp压缩空间的思路,也是很重要的,我在其它文章中有提过,在这里就不写了)

    public static int solution3(int nLevel, int kChess) {
        if (kChess == 1) {
            return nLevel;
        }
        int[] preArr = new int[nLevel + 1];
        int[] curArr = new int[nLevel + 1];
        for (int i = 1; i != curArr.length; i++) {
            curArr[i] = i;
        }//初始化
        for (int i = 1; i != kChess; i++) {
                  //先交换
            int[] tmp = preArr;
            preArr = curArr;
            curArr = tmp;
                  //然后打新的一行
            for (int j = 1; j != curArr.length; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 1; k != j + 1; k++) {
                    min = Math.min(min, Math.max(preArr[k - 1], curArr[j - k]));
                }
                curArr[j] = min + 1;
            }
        }
        return curArr[curArr.length - 1];
    }
 

四边形不等式优化
 

四边形不等式是一种比较常见的优化动态规划的方法

定义:如果对于任意的a1≤a2<b1≤b2,有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1],那么m[i,j]满足四边形不等式。

对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明:

设mk[i,j]=m[i,k]+m[k,j],s[i,j]=d

对于任意k<d,有mk[i,j]≥md[i,j](这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似),接下来只要证明mk[i+1,j]≥md[i+1,j],那么只有当s[i+1,j]≥s[i,j]时才有可能有mk[i+1,j]≥md[i+1,j]

(mk[i+1,j]-md[i+1,j])-(mk[i,j]-md[i,j])

=(mk[i+1,j]+md[i,j])-(md[i+1,j]+mk[i,j])

=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])-(m[i+1,d]+m[d,j]+m[i,k]+m[k,j])

=(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k])

∵m满足四边形不等式,∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]

∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0

∴s[i,j]≤s[i+1,j],同理可证s[i,j-1]≤s[i,j]

证毕

 

通俗来说,

优化策略1)我们在求k+1手机n层楼时,最后发现,第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n层楼时,第一个手机的策略就不用尝试m层以上的楼了。

优化策略2)我们在求k个手机n层楼时,最后发现,第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n+1层楼时,就不用尝试m层以下的楼了。

    public static int solution4(int nLevel, int kChess) {
        if (kChess == 1) {
            return nLevel;
        }
        int[][] dp = new int[nLevel + 1][kChess + 1];
        for (int i = 1; i != dp.length; i++) {
            dp[i][1] = i;
        }
        int[] cands = new int[kChess + 1];
        for (int i = 1; i != dp[0].length; i++) {
            dp[1][i] = 1;
            cands[i] = 1;
        }
        for (int i = 2; i < nLevel + 1; i++) {
            for (int j = kChess; j > 1; j--) {
                int min = Integer.MAX_VALUE;
                int minEnum = cands[j];
                int maxEnum = j == kChess ? i / 2 + 1 : cands[j + 1];
                              //优化策略
                for (int k = minEnum; k < maxEnum + 1; k++) {
                    int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
                    if (cur <= min) {
                        min = cur;
                        cands[j] = k;//最优解记录层数
                    }
                }
                dp[i][j] = min + 1;
            }
        }
        return dp[nLevel][kChess];
    }
注:对于四边形不等式的题目,比赛时不需要严格证明

通常的做法是打表出来之后找规律,然后大胆猜测,显然可得。(手动滑稽)

 

换一种思路
 

有时,最优解并不是优化来的。

当你对着某个题冥思苦想了好久,无论如何也不知道怎么把时间优化到合理范围,可能这个题的最优解就不是这种思路,这时,试着换一种思路思考,可能会有奇效。

(比如训练时一道贪心我死活往dp想,肝了两个小时以后,不主攻这个方向的队友三分钟就有贪心思路了,泪目,不要把简单问题复杂化)

 

我们换一种思路想问题:

原问题:n层楼,k个手机,最多测试次数

反过来看问题:k个手机,扔m次,最多能确定多少层楼?

我们定义dp[i][j]:i个手机扔j次能确定的楼数。

分析情况:依旧是看第一部手机在哪层扔的决策,同样,我们的决策首先要保证能确定从1层某一段,而不能出现次数用完了还没确定好的情况。以这个为前提,保证了每次扔的楼层都是最优的,就能求出结果。

依旧是取最坏情况:max(情况1,情况2)

情况1)第一个手机碎了,我们就需要用剩下的i个球和j-1次测试次数往下去测,dp[i][j-1]。那我们能确定的层数是无限的,因为本层以上的无限层楼都不会被摔坏。dp[i][j-1]+无穷=无穷

情况2)第一个手机没碎,那我们就看i-1个手机扔j-1次能确定的楼数(向上试)+当前楼高h

归纳表达式,要取最差情况,所以就是只有情况2:dp[i][j]=dp[i-1][j-1]+h

那这个h到底是什么呢?取决于我敢从哪层扔。因为次数减了一次,我们还是要考虑i个球和j-1次的最坏情况能确定多少层,我才敢在层数+1的地方扔。(这是重点)

也就是dp[i][j-1]的向上一层:h=dp[i][j-1]+1

总:max(情况1,情况2)=max(无穷,dp[i-1][j-1]+dp[i][j-1]+1)=dp[i-1][j-1]+dp[i][j-1]+1

这是解决k个手机,扔m次,最多能确定多少层楼?

原问题是n层楼,k个手机,最多测试次数。

所以我们在求的过程中,何时能确定的层数大于n,输出扔的次数即可

 

最优解

 


我们知道完全用二分扔需要logN+1次,这也绝对是手机足够情况下的最优解,我们做的这么多努力都是因为手机不够摔啊。。。。所以当我们的手机足够用二分来摔时,直接求出logN+1即可。

 

当然,我们求dp需要左边的值和左上的值:

依旧可以压缩空间,从左往右更新,previous记录左上的值。

求自己时也要注意记录,否则更新过后,后面的要用没更新过的值(左上方)就找不到了。

记录之后,求出当前数值,把记录的temp值给了previous即可。

    public static int solution5(int nLevel, int kChess) {
        int bsTimes = log2N(nLevel) + 1;
        if (kChess >= bsTimes) {
            return bsTimes;
        }
        int[] dp = new int[kChess];
        int res = 0;
        while (true) {
            res++;//压缩空间记得记录次数
            int previous = 0;
            for (int i = 0; i < dp.length; i++) {
                int tmp = dp[i];
                dp[i] = dp[i] + previous + 1;
                previous = tmp;
                if (dp[i] >= nLevel) {
                    return res;
                }
            }
        }
    }
 
    public static int log2N(int n) {
        int res = -1;
        while (n != 0) {
            res++;
            n >>>= 1;
        }
        return res;
    }
 

 

 

 

本题只是填空题,第一种方法就完全能算出来,就是为了追求最优解,追求思维的锻炼。写下了本文。

 

 

测试:


暴力:                        O(N!)

DP:                            O(N*N*K)  O(N*K)

压空间:                    O(N*N*K)  O(N)

四边形不等式优化     O(N*N)       

最优:                         O(K*M)    O(N)

        long start = System.currentTimeMillis();
        solution1(30, 2);
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + " ms");
        start = System.currentTimeMillis();
        solution2(30, 2);
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + " ms");
        start = System.currentTimeMillis();
        solution3(30, 2);
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + " ms");
        start = System.currentTimeMillis();
        solution4(30, 2);
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + " ms");
        start = System.currentTimeMillis();
        solution5(30, 2);
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + " ms");
/*
结果:
cost time: 7043 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
*/
暴力时间实在是太久了,只测一个30,2

 

后四种方法测的大一些(差点把电脑测炸了,cpu100内存100):

solution(100000, 10):

solution2 cost time: 202525 ms
solution3 cost time: 38131 ms
solution4 cost time: 11295 ms
solution5 cost time: 0 ms

 

感受最优解的强大:

solution5(1000 000 000,100):0 ms

solution5(1000 000 000,10):0 ms

最优解永远都是0 ms,我也是服了。。

 

对比方法,在时间复杂度相同的条件下,空间复杂度一样会影响时间,因为空间太大的话,申请空间是相当浪费时间的。并且空间太大电脑会炸,所以不要认为空间不重要。
--------------------- 
作者:hebtu666 
来源:CSDN 
原文:https://blog.csdn.net/hebtu666/article/details/84789853 
版权声明:本文为博主原创文章,转载请附上博文链接!

收藏 转发 评论 2

老师厉害

杨伟彬

厉害