[MeetCoder] Crossing Bridge - Eason Liu - 博客园


[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:
 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,则:
  1. TS = T5 + T1 + T4 + T1 + T3 + T1 + T2
  2. = 18 + 1 + 6 + 1 + 3 + 1 + 2
  3. = 32
然而这样计算的总时间已经超过了 30 分钟,因此显然并不是最优的方法。这里暂时将这个方法定义为「方法一」。
回家仔细思考后发现有更快地通过方式。这里约定每过一次桥为「一趟」,则过桥方式文字表述如下:
第一趟:小明和爸爸一起通过,所用时间为T2
第二趟:小明返回,所用时间为T1
第三趟:爷爷和妈妈一起通过,所用时间为T5
第四趟:爸爸返回,所用时间为T2
第五趟:小明和弟弟一起通过,所用时间为T3
第六趟:小明返回,所用时间为T1
第七趟:小明和爸爸一起通过,所用时间为T2
因此总时间为:
  1. TS = T2 + T1 + T5 + T2 + T3 + T1 + T2
  2. = 2 + 1 + 18 + 2 + 3 + 1 + 2
  3. = 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 地,两侧数字分别表示这一趟过桥结束后两地所有的人:
  1. A B
  2. 3, 4 ====> 1, 2
  3. 1, 3, 4 <==== 2
  4. 1 ====> 2, 3, 4
  5. 1, 2 <==== 3, 4
  6. ====> 1, 2, 3, 4
所需时间为:
  1. TS2 = T2 + T1 + T4 + T2 + T2
  2. = 2 + 1 + 3 + 2 + 2
  3. = 10
而「方法一」方式如下图:
  1. A B
  2. 2, 3 ====> 1, 4
  3. 1, 2, 3 <==== 4
  4. 2 ====> 1, 3, 4
  5. 1, 2 <==== 3, 4
  6. ====> 1, 2, 3, 4
所需时间为:
  1. TS1 = T4 + T1 + T3 + T1 + T2
  2. = 3 + 1 + 2 + 1 + 2
  3. = 9
此时「方法一」所用时间就短于「方法二」,思考后发现这两种方法的区别在于前三趟,列出公式比较:
  1. 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分钟
所以能够活学图论的话,这类智力问题就变成了图论的入门级的问题。
Read full article from [MeetCoder] Crossing Bridge - Eason Liu - 博客园

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts