在我的一个群里，小伙伴发了一道题，考察下算法，自己试着想了想，拿出来一起看下吧，下面是题目：
在漆黑的夜里，N 位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N 个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N 人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这 N 人尽快过桥。（ ACM 难度系数 ：5）
分析问题
面对毫无头绪的问题只能慢慢分析喽，首先把 N 个人需要的时间放到一个数组 T[n] 里面吧，时间的长短是不定的，因此先排为升序；既然是 N 个人，那就从 N = 1开始分析，找找规律吧：
1
2
3
4
N ＝ 1； 当然需要花费 T[0] 喽（数组下标从 0 开始）；
N ＝ 2； 需要花费 T[0] ＋ T[1]，也就是两个人一起过去；
N ＝ 3； 需要花费 T[0] ＋ T[1] ＋ T[2]; 很容易想到的是让最快那个人去送最慢的那个花费了 T[2]；他返回来花费了 T[0]，然后最快的这个和剩下的这个速度不是很快的一起过去花费了 T[1]；
N ＝ 4； 这个怎么过？陷入沉思之中...
这道题目的说白了就是送人，时间由最慢的那个人决定，而且送完一个，还要返回来接着送，所以我们不可能让一个走的慢的人来充当这个‘摆渡’的，既然如此，那么我们就从走的慢的人下手吧，因为他不能充当‘摆渡’的，那么他早晚都要‘坐船’走呀，所以 N ＝ 4 就转化为花最少的时间送走‘坐船’的；（为了简化描述，按照时间升序的顺序将4人命名为a,b,c,d）下面分析下：
- 根据 N = 3 的经验，我们很容易想到让 a 去送每一个人，送完一个就返回，接着送最慢的，如此3次；
- 可是还有一种送法，a 送 b,a 回来；c 送 d，b 回来；a 送 b，也可以，而且时间不一定哪个短，因此要比较下哪个短；
- 4个人不可能就这两种送法啊，还有别的，不过时间都要比这两个长；
当 N > 4 呢？其实根据 N = 4 的情况来看，这就是一个如何先送走最慢的的2个人的问题，因此 N > 4 的时候，先不考虑中间的，把最快的，次快的，最慢的，此慢的拿出来摆渡，然后问题就变成了 N - 2 的问题了！当然可以写个递归了！
下面是主要代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sumTimeNeed = 0;
while (size > 3) {
int time1 = a[1] + a[0] + a[size-1] + a[1] ;
int time2 = a[size-1] + a[0] + a[size-2] + a[0];
size -= 2;
sumTimeNeed += MIN(time1, time2);
}
if (size == 3) {
sumTimeNeed += a[0] + a[1] + a[2];
}else if (size == 2){
sumTimeNeed += a[1];
}else if (size == 1){
sumTimeNeed += a[0];
}
return sumTimeNeed;
欢迎去我的 GitHub 建议
1.最古老的过河问题
一个农民携带一只狼，一只羊和一棵白菜，要借助一条小船过河。小船上除了农民只能再带狼、羊、白菜中的一样。而农民不在时，狼会吃羊，羊会吃白菜。农民最少需要几趟才能安全过河呢？
2.人鬼殊途
三个鬼与三个人都要过河。河中只有一条小船，可容两人(鬼)。而且无论在船上或在岸上，每边的鬼数量如果多于人,鬼就会把人吃掉。最少需要几趟才能安全过河
3.道士与和尚
四个道士与四个和尚四个老道士与四个和尚分别在一条河的两岸，都要到河的对岸去。河中只有一条小船，可容两人。只有一个道士和一个和尚会划船。而且无论在船上或在岸上，道士的数量都不能超过和尚的数量。最少需要几趟才能安全过河
4.夫妻过河
两对夫妻两对夫妻要过河，河中只有一条小船，可容两人。两个丈夫都不愿让自己的妻子和另一个男人在一起，除非自己也在场。 最少需要几趟才能安全过河？
5.一家人及警察与犯人
现有一条河，共有八个人要过河，分别是爸爸，妈妈，两个儿子，两个女儿，一个警察，一个犯人．现有一条木伐，一次最多载两个人，在这八个人中，有妈妈，爸爸，警察会开船，即这个船上必须有爸爸，妈妈，警察三个中的一个，船才会开动．船过去无法自动回来．并且要避免以下三件事发生，１，警察不在犯人会伤害一家六口．２，爸爸不在，妈妈会伤害儿子．３，妈妈不在，爸爸会伤害女儿． 最少需要几趟才能安全过河
6.虎毒不食子
三只大老虎A、B、C和各自的小老虎a.b.c；其中只有A、B、C和a会划船；如果小老虎不和自己的母亲在一起就会被其他大老虎吃掉；只有一条船；船上可以坐一只大老虎和任意的小老虎；问：最少需要几趟才能安全过河
7.八仙过海
铁拐李 、汉钟离 、 张果老 、蓝采和 、 何仙姑 、 吕洞宾 、 韩湘子 、 曹国舅一同过海。小船只能容下三人，而且只有道铁拐李 、汉钟离、韩湘子会划船。如果韩湘子不在，曹国舅会攻击所有人；如果铁拐李不在，汉钟离会攻击张果老和蓝采和；如果汉钟离不在，铁拐李会攻击何仙姑 、 吕洞宾。请问最少需要几趟才能安全过海？
