漫画:微软面试挂在了这道题
尊重原创，转载请务必保留文末的二维码
题目
馒头和奶昔是对dog夫妻，它们有两个baby：淘淘和皮皮。一天晚上，它们一家四口出去游玩，回家过程中迷路了，困在了一座桥边上。馒头家只带了一个手电筒，由于是荒山夜晚，没有手电筒谁也不敢私自过桥。桥呢又比较窄，一次最多只能过2只狗。馒头家每个成员单独过桥所需要的时间依次是：1min、2min、5min、8min。如果两个人一起过桥，需耗费的时间是走得慢的那个成员所需要的时间。馒头一家都想早点过桥回家，现在请你帮助它们设计一个过桥方案，使的总耗费时间最少。馒头脑子不太好用，希望你能够给ta一个通用的方案，以便下次和朋友出去玩时使用，即帮忙给出一个适用任何成员数量的最优过桥方案。注：每个成员单独过桥的时间是已知的。
三天过去了.....
分析
题目主要就以下两个点：
-
输入是：成员数量，以及每个成员单独过桥的时间。
-
输出是所有人过桥的最短时间
问题是怎样的方案耗时才是最短呢？显然，第一印象是：过桥最快的那个成员，依次把其余成员带过桥（因为只有一个手电筒）。比如，下面这个案例：
A、B、C、D四个人的过桥时间分别是：1、8、9、10分钟。这种情况下的最短过桥时间方案是：
-
A送D过桥，10分钟
-
A回去，1分钟
-
A送C过桥，9分钟
-
A回去，1分钟
-
A送B过桥，8分钟
一共10+1+9+1+8=29分钟
但是，最优解还可能发生在另外一种情况，这也是很容易想到的情况：最慢的成员一定要过桥，那么它的时间是必须花费的，那么谁和最慢的成员过桥会最省时间呢？你猜对了，就是过桥最慢的成员带着次慢的成员一起过桥，比如下面这个案例：
还是上面的场景，更改下各自的过桥时间，A、B、C、D单独过桥的时间依次为：1、2、5、8分钟。此时最短过桥方案是：
-
A和B先过桥，花费2分钟
-
A回去，花费1分钟
-
C和D一起过桥，花费8分钟
-
B回去，花费2分钟
-
A和B一起过桥，2分钟
一共花费：2+1+8+2+2=15分钟
上面第一步是最快的两个先过桥，因为第二快的成员只有要回去接人，也就是最慢和次慢的成员过桥后不能再让它们把手电筒送回来。所以是最快的两个先过桥，然后是最慢的两个过桥，最后是次快的成员把手电筒送回去。
上面是四个人的情况，任意数量成员的时候，我们只需要重复上述过程就好，什么意思呢？
仔细看上面两个案例最优解的前四步，有什么共同点呢？对，这两个方案的前四步都是把两个人送过桥了。还没明白吗：如果有8个人，走完前四步还剩6个人，继续重复这个过程，直到未过桥成员数量到达边界值，边界值包含：
-
还剩3个成员未过桥
-
还剩2个成员未过桥
-
还剩1个成员未过桥
还剩3个成员时，需要的时间必定是：t1+t2+t3
还剩2个成员时，需要的时间必定是：max(t1,t2)
还剩1个成员时，需要的时间必定是：t1
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);
}
}
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
热文推荐
