漫画:微软面试挂在了这道题

电玩女神 2022-02-16 11:31 359阅读 0赞

> 尊重原创，转载请务必保留文末的二维码

![1240][]

![1240 1][]

![1240 2][]

![1240 3][]

![1240 4][]

![1240 5][]

![1240 6][]

![1240 7][]

![1240 8][]

**题目**

馒头和奶昔是对dog夫妻，它们有两个baby：淘淘和皮皮。一天晚上，它们一家四口出去游玩，回家过程中迷路了，困在了一座桥边上。馒头家只带了一个手电筒，由于是荒山夜晚，没有手电筒谁也不敢私自过桥。桥呢又比较窄，一次最多只能过2只狗。馒头家每个成员单独过桥所需要的时间依次是：1min、2min、5min、8min。如果两个人一起过桥，需耗费的时间是走得慢的那个成员所需要的时间。馒头一家都想早点过桥回家，现在请你帮助它们设计一个过桥方案，使的总耗费时间最少。馒头脑子不太好用，希望你能够给ta一个通用的方案，以便下次和朋友出去玩时使用，即帮忙给出一个适用任何成员数量的最优过桥方案。注：每个成员单独过桥的时间是已知的。

![1240 9][]

![1240 10][]

![1240 11][]

![1240 12][]

**三天过去了…**

![1240 13][]

![1240 14][]

![1240 15][]

![1240 16][]

![1240 17][]

**分析**

题目主要就以下两个点：

1.  输入是：成员数量，以及每个成员单独过桥的时间。
2.  输出是所有人过桥的最短时间

问题是怎样的方案耗时才是最短呢？显然，第一印象是：过桥最快的那个成员，依次把其余成员带过桥（因为只有一个手电筒）。比如，下面这个案例：

A、B、C、D四个人的过桥时间分别是：1、8、9、10分钟。这种情况下的最短过桥时间方案是：

1.  A送D过桥，10分钟
2.  A回去，1分钟
3.  A送C过桥，9分钟
4.  A回去，1分钟
5.  A送B过桥，8分钟

一共10+1+9+1+8=29分钟

但是，最优解还可能发生在另外一种情况，这也是很容易想到的情况：最慢的成员一定要过桥，那么它的时间是必须花费的，那么谁和最慢的成员过桥会最省时间呢？你猜对了，就是过桥最慢的成员带着次慢的成员一起过桥，比如下面这个案例：

还是上面的场景，更改下各自的过桥时间，A、B、C、D单独过桥的时间依次为：1、2、5、8分钟。此时最短过桥方案是：

1.  A和B先过桥，花费2分钟
2.  A回去，花费1分钟
3.  C和D一起过桥，花费8分钟
4.  B回去，花费2分钟
5.  A和B一起过桥，2分钟

一共花费：2+1+8+2+2=15分钟

上面第一步是最快的两个先过桥，因为第二快的成员只有要回去接人，也就是最慢和次慢的成员过桥后不能再让它们把手电筒送回来。所以是最快的两个先过桥，然后是最慢的两个过桥，最后是次快的成员把手电筒送回去。

![1240 18][]

![1240 19][]

![1240 20][]

上面是四个人的情况，任意数量成员的时候，我们只需要重复上述过程就好，什么意思呢？

仔细看上面两个案例最优解的前四步，有什么共同点呢？对，这两个方案的前四步都是把两个人送过桥了。还没明白吗：如果有8个人，走完前四步还剩6个人，继续重复这个过程，直到未过桥成员数量到达边界值，边界值包含：

1.  还剩3个成员未过桥
2.  还剩2个成员未过桥
3.  还剩1个成员未过桥

还剩3个成员时，需要的时间必定是：t1+t2+t3

还剩2个成员时，需要的时间必定是：max(t1,t2)

还剩1个成员时，需要的时间必定是：t1

![1240 21][]

![1240 22][]

**java 代码**

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    public class MicrosoftInterview { 
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入总人数:");
            int num = sc.nextInt();
    
            if(num<=0)  return;
    
            System.out.println("请输入上面每个成员的过桥时间，用空格隔开!");
            ArrayList<Integer> list = new ArrayList<>(num);
    
            for(int i=0;i<num;i++)
                list.add(sc.nextInt());
    
            Collections.sort(list);//默认升序排列
    
            int result = 0;
    
          //指向最慢的成员，先处理最慢的成员
            int i = num - 1;
            for(;i>2;i-=2) {            
                 //以下list[i]是list.get(i)的简写 
    
                //最快的依次将最慢的两个人送过桥，并回去。
                //1.最快和最慢的一起,花费时间:list[i]
                //2.最快回去,花费时间:list[0]
                //3.最快的和次慢的一起，花费时间:list[i-1]
                //4.最快的回去,花费时间:list[0]
                int t1 = 2*list.get(0) + list.get(i)+ list.get(i-1);
    
                //1.最快的两个一起过桥，花费时间:list[1];
                //2.最快的回来，花费时间:list[0];
                //3.最慢的两个过桥,花费时间:list[i]
               //4.次快的回去,花费时间:list[1] 
                int t2 = list.get(0) + 2*list.get(1)+ list.get(i);
    
                if(t1<=t2)
                    result += t1;
                else
                    result += t2;
    
                //不管哪一种方案，执行完之后最慢的2个人都过桥了
                //所以for循环中i每次后 减2
            }
    
            if(i==2)//剩余三人，因为下标从0开始的
                result += list.get(0)+  list.get(1) +  list.get(2);
            else if(i==1)
                result += list.get(1);
            else 
                result += list.get(0);
    
          System.out.println(num+"成员过桥最少花费时间是: "+result);
        }
    }

![1240 23][]

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：公众号后台回复“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；公众号后台回复“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240 24]

**热 文推 荐**

☞[微软福利：github重大更新][github]

☞[漫画:趣味烧绳子问题(vivo面试题)][vivo]

☞[彻底搞定java反射][java]

[1240]: /images/20220216/36f756318be24f56b8da7b2699a02b73.png
[1240 1]: /images/20220216/9e71ca343ba145f19ab1c9ceb05b65e5.png
[1240 2]: /images/20220216/d509b5f8d2244b7f8b68db6e82974dc9.png
[1240 3]: /images/20220216/b022fb0a818b4871be4badf41da21b32.png
[1240 4]: /images/20220216/7911ba7f42b8452e9efcad0335375617.png
[1240 5]: /images/20220216/b8fd0c5298c4466ea280fd6a4455f814.png
[1240 6]: /images/20220216/a8f25210face4410b023533d0580aa1d.png
[1240 7]: /images/20220216/02fb13c5b2164f41b2a6cc902ed48101.png
[1240 8]: /images/20220216/c2d2ea6bc7344832a0473de8bf8d0ea8.png
[1240 9]: /images/20220216/a24b42a92526457ca392371b18b16044.png
[1240 10]: /images/20220216/431f1c379da64a08bb157598e57aff12.png
[1240 11]: /images/20220216/b8533b6e6a9a40e394a7a1e52c7522b7.png
[1240 12]: /images/20220216/63ad21780a8246b8833f47acbb7ffbc5.png
[1240 13]: /images/20220216/169dbbc64bec4a88902598344ba47dbe.png
[1240 14]: /images/20220216/eef673ee7b0a4363b708ecfb6c5389eb.png
[1240 15]: /images/20220216/33069fdd9a96441591e86144312f6fd1.png
[1240 16]: /images/20220216/1b89f2c44ee74aeaaf25a788e278ec15.png
[1240 17]: /images/20220216/8637ef0ca0f64af39c824ab7b2f030a6.png
[1240 18]: /images/20220216/0bdd942da1004348aedfe1c6ad83f546.png
[1240 19]: /images/20220216/377b1082f50a4b579c3c6b645c19d688.png
[1240 20]: /images/20220216/e6ffc823006a41bc9e8f69fc1b066d93.png
[1240 21]: /images/20220216/d4ecdf9f7f22480485ef3265dba57edc.png
[1240 22]: /images/20220216/814e48c4981f44619b918f994bbde245.png
[1240 23]: /images/20220216/db1df5caa26b42a1bd74bb3c05a7e1ba.png
[1240 24]: /images/20220216/70cb2e038f684a719e123b8aa632b797.png
[github]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484929&idx=1&sn=e2d6d8ccb1d0ac25da184163587cd6f7&chksm=eb5125f5dc26ace3e612eea0d3c959af424585c7d8f402118bdf607db875d5a519055bc0587a&scene=21#wechat_redirect
[vivo]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484869&idx=1&sn=003a48fd4395cec57b5e20e550f6d62c&chksm=eb512631dc26af275b38889c358eee60e28e4761cbd6761e39c9dc1f69447e643f88b11318c8&scene=21#wechat_redirect
[java]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484801&idx=1&sn=3fdbf0dddf8ef7afa6fc546214c9c2f6&chksm=eb512675dc26af6368dba869e80bda3169abbbf29d4ecaaa040abc8be8ea9ffadd2e98616479&scene=21#wechat_redirect