在我的一个群里,小伙伴发了一道题,考察下算法,自己试着想了想,拿出来一起看下吧,下面是题目:

在漆黑的夜里,N 位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N 个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N 人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这 N 人尽快过桥。( ACM 难度系数 :5)

分析问题

面对毫无头绪的问题只能慢慢分析喽,首先把 N 个人需要的时间放到一个数组 T[n] 里面吧,时间的长短是不定的,因此先排为升序;既然是 N 个人,那就从 N = 1开始分析,找找规律吧:

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)下面分析下:

  1. 根据 N = 3 的经验,我们很容易想到让 a 去送每一个人,送完一个就返回,接着送最慢的,如此3次;
  2. 可是还有一种送法,a 送 b,a 回来;c 送 d,b 回来;a 送 b,也可以,而且时间不一定哪个短,因此要比较下哪个短;
  3. 4个人不可能就这两种送法啊,还有别的,不过时间都要比这两个长;

当 N > 4 呢?其实根据 N = 4 的情况来看,这就是一个如何先送走最慢的的2个人的问题,因此 N > 4 的时候,先不考虑中间的,把最快的,次快的,最慢的,此慢的拿出来摆渡,然后问题就变成了 N - 2 的问题了!当然可以写个递归了!

下面是主要代码

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.一家人及警察与犯人

现有一条河,共有八个人要过河,分别是爸爸,妈妈,两个儿子,两个女儿,一个警察,一个犯人.现有一条木伐,一次最多载两个人,在这八个人中,有妈妈,爸爸,警察会开船,即这个船上必须有爸爸,妈妈,警察三个中的一个,船才会开动.船过去无法自动回来.并且要避免以下三件事发生,1,警察不在犯人会伤害一家六口.2,爸爸不在,妈妈会伤害儿子.3,妈妈不在,爸爸会伤害女儿. 最少需要几趟才能安全过河

6.虎毒不食子

三只大老虎A、B、C和各自的小老虎a.b.c;其中只有A、B、C和a会划船;如果小老虎不和自己的母亲在一起就会被其他大老虎吃掉;只有一条船;船上可以坐一只大老虎和任意的小老虎;问:最少需要几趟才能安全过河

7.八仙过海

铁拐李 、汉钟离 、 张果老 、蓝采和 、 何仙姑 、 吕洞宾 、 韩湘子 、 曹国舅一同过海。小船只能容下三人,而且只有道铁拐李 、汉钟离、韩湘子会划船。如果韩湘子不在,曹国舅会攻击所有人;如果铁拐李不在,汉钟离会攻击张果老和蓝采和;如果汉钟离不在,铁拐李会攻击何仙姑 、 吕洞宾。请问最少需要几趟才能安全过海?

有兴趣的快去 AC 吧!