debugly/acm

业余时间我会去AC一道题，然后写篇博客，拿来分享

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;