[MeetCoder] Crossing Bridge - Eason Liu - 博客园
N people wish to cross a bridge at night. It's so dark around there that they have to cross the bridge under the help of a little lamp. Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such that a maximum of 2 people may cross at a time.
Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one. How fast can you get all N people over the bridge?
Input
The input should be a list of N positive integers, where N is less than or equal to 1,000. And each integer of the list should be less than or equal to 100.
Output
The output should be the minimum time that all the people can cross the bridge.过桥问题！主要参考：http://blog.csdn.net/morewindows/article/details/7481851
X. Brute Force:
http://www.huangxc.com/cross-bridge/
微软过桥问题的图论解法
N people wish to cross a bridge at night. It's so dark around there that they have to cross the bridge under the help of a little lamp. Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such that a maximum of 2 people may cross at a time.
Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one. How fast can you get all N people over the bridge?
Input
The input should be a list of N positive integers, where N is less than or equal to 1,000. And each integer of the list should be less than or equal to 100.
Output
The output should be the minimum time that all the people can cross the bridge.过桥问题！主要参考：http://blog.csdn.net/morewindows/article/details/7481851
X. Brute Force:
3 int _bridge(vector<int> &v, int n) { 4 if (n == 0) return 0; 5 if (n == 1) return v[0]; 6 if (n == 2) return v[1]; 7 if (n == 3) return v[0] + v[1] + v[2]; 8 int res = 0; 9 int a = v[0], b = v[1], x = v[n-2], y = v[n-1]; 10 if (2 * b > a + x) res += 2 * a + x + y; 11 else res += a + 2 * b + y; 12 return res + _bridge(v, n - 2); 13 } 14 public: 15 int bridge(vector<int> &v) { 16 sort(v.begin(), v.end()); 17 return _bridge(v, v.size()); 18 }
http://www.huangxc.com/cross-bridge/
小明和爸爸、妈妈、弟弟、爷爷一起要通过一座桥，由于是夜晚，必须打灯才能通过。桥上一次最多只能通过两人。小明过桥需要 1 分钟，爸爸需要 2 分钟，弟弟需要 3 分钟，妈妈需要 6 分钟，爷爷需要 18 分钟，两人一起过桥时时间按速度较慢者过桥时间算。他们只有一盏灯，且等只能点亮 30 分钟，问怎样过桥所用时间最短，并用程序实现。
当时第一反应是让速度最快的人来回护送其他人通过，那么所用总时间就是送爷爷的时间 + 小明返回时间 + 送妈妈时间 + 小明返回时间 + 送弟弟时间 + 小明返回时间 + 和爸爸一起通过时间，设小明、爸爸、弟弟、妈妈、爷爷过桥所用时间分别为 T1、T2、T3、T4、T5，所用总时间为 TS，则：
- TS = T5 + T1 + T4 + T1 + T3 + T1 + T2
- = 18 + 1 + 6 + 1 + 3 + 1 + 2
- = 32
然而这样计算的总时间已经超过了 30 分钟，因此显然并不是最优的方法。这里暂时将这个方法定义为「方法一」。
回家仔细思考后发现有更快地通过方式。这里约定每过一次桥为「一趟」，则过桥方式文字表述如下：
第一趟：小明和爸爸一起通过，所用时间为T2。
第二趟：小明返回，所用时间为T1。
第三趟：爷爷和妈妈一起通过，所用时间为T5。
第四趟：爸爸返回，所用时间为T2。
第五趟：小明和弟弟一起通过，所用时间为T3。
第六趟：小明返回，所用时间为T1。
第七趟：小明和爸爸一起通过，所用时间为T2。
因此总时间为：
- TS = T2 + T1 + T5 + T2 + T3 + T1 + T2
- = 2 + 1 + 18 + 2 + 3 + 1 + 2
- = 29
以上方法定义为「方法二」。这样更快之所以更快是因为最慢的人和次慢的人一起通过，就可以减少总时间。总时间的决定因素在于速度慢的人需要花费多少时间而不是速度快的人花费多少，这有点类似于木桶原理。
将此问题一般化，假设有 N 个人过桥，所需时间从少到多依次为 T1， T2， T3， ···， TN-1， TN，（同时 N 个人分别表示为 1， 2， 3， ···， N-1， N），那么问题要稍微复杂一些，不能单纯的使用「方法二」让最慢的和次慢的一起通过，因为如果次慢者的速度和次快者速度相差不大，那么这也许就不再是最优的方法，考虑如下情况：
四个人所需时间分别为：
T1 = 1
T2 = 2
T3 = 2
T4 = 3
则「方法二」过桥方式如下图，约定 A 地为未过桥时的地方，B 地为过桥后的位置，
====> 符号表示从 A 地过桥至 B 地，<==== 表示从 B 地过桥返回 A 地，两侧数字分别表示这一趟过桥结束后两地所有的人：
A 地 B 地3, 4 ====> 1, 21, 3, 4 <==== 21 ====> 2, 3, 41, 2 <==== 3, 4====> 1, 2, 3, 4
所需时间为：
- TS2 = T2 + T1 + T4 + T2 + T2
- = 2 + 1 + 3 + 2 + 2
- = 10
而「方法一」方式如下图：
A 地 B 地2, 3 ====> 1, 41, 2, 3 <==== 42 ====> 1, 3, 41, 2 <==== 3, 4====> 1, 2, 3, 4
所需时间为：
- TS1 = T4 + T1 + T3 + T1 + T2
- = 3 + 1 + 2 + 1 + 2
- = 9
此时「方法一」所用时间就短于「方法二」，思考后发现这两种方法的区别在于前三趟，列出公式比较：
- TS1 - TS2 = (T1 + T3) - (T2 + T2)
因此当最快者和次慢者所用时间之和大于 2 倍次快者所用时间时，「方法二」所用时间短，反之则「方法一」所用时间短。当然四个人时还有更多的方法可以过桥，但其余方法所用时间都明显会大于「方法一」和「方法二」。
推广到更多人时，依然以每四个人为最小单位（当人数为三人时最短时间就是单纯的三人所需时间相加）进行如上的判断，使用「方法一」或者「方法二」，这样看作一个整体计算一次后，A 地剩余人数就减少 2，再递归调用，直至 A 地剩余人数少于四人。
http://blog.csdn.net/morewindows/article/details/7481851 for (i = 0; i < n; i++)
cin>>a[i];
qsort(a, n, sizeof(a[0]), cmp);
sum = 0;
for (i = n - 1; i > 2; i = i - 2)
{
//最小者将最大2个送走或最小2个将最大2个送走
if (a[0] + a[1] + a[1] + a[i] < a[0] + a[0] + a[i - 1] + a[i])
sum = sum + a[0] + a[1] + a[1] + a[i];
else
sum = sum + a[0] + a[0] + a[i - 1] + a[i];
}
if (i == 2)
sum = sum + a[0] + a[1] + a[2];
else if (i == 1)
sum = sum + a[1];
else
sum = a[0];
cout<<"最短过桥时间为："<<sum<<endl;
http://m.blog.csdn.net/blog/asuxiexie/38533379 sort(s,s+a);
int ans=a,cne,sum=0,d,e;
while(ans>3)
{
int sum1=2*s[0]+s[ans-2]+s[ans-1];
int sum2=2*s[1]+s[0]+s[ans-1];
if(sum1>sum2)
sum+=sum2;
else
sum+=sum1;
ans-=2;
}
if(ans==3)
printf("%d\n",sum+=s[0]+s[1]+s[2]);
else
printf("%d\n",sum+=s[1]);
while(a>3)
{
if(s[0]+s[a-2]<2*s[1])
printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[a-1],s[0],s[0],s[a-2],s[0]);
else
printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[1],s[0],s[a-2],s[a-1],s[1]);
a-=2;
}
if(a==3)
printf("%d %d\n%d\n%d %d\n",s[0],s[2],s[0],s[0],s[1]);
else
printf("%d %d\n",s[0],s[1]);
http://www.acmerblog.com/POJ-2573-Bridge-blog-798.html微软过桥问题的图论解法
微软的过桥问题说的是4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？
这个问题如果用图论来建模的话，就可以以4个人在桥两端的状态来作为节点来构造一个有向图，如下图所示，以已经过桥了的人的状态作为图的节点，初始时没有人过桥，所以以空表示，第一轮有两个人过桥，有6种可能的组合，(1，2)（1，5）（1，10）（2，5）（2，10）（5，10），从空的状态转换到这些状态的需要的时间分别为2，5，10，5，10，10分钟，时间就作为有向边的权值。当有两个人过桥后，需要一个人拿手电筒回去接其他人，这时有四种可能的情况，分别是1，2，5，10中的一人留在了河的对岸，（1，2）这种状态只能转换到（1）（2）两种状态，对应的边的权值分别为2，1分钟，（1，2）转换到（1）时也就是2返回了，返回需要耗时2分钟，以此类推可以建立以下的图论模型。
要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出（空）节点到（1，2，5，10）节点间的最短路径。
根据Dijkstra最短路径算法很容易求出其最短路径，如图中的粗线所示。
这样总时间为2＋1＋10＋2＋2＝17分钟
所以能够活学图论的话，这类智力问题就变成了图论的入门级的问题。
