Skip to content
业余时间我会去AC一道题,然后写篇博客,拿来分享
Objective-C++ C++
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
过河问题
LICENSE
README.md

README.md

ACM

<这不是我 AC 的第一道题,可她是我第一次写的博客>


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

在漆黑的夜里,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;
You can’t perform that action at this time.