Description
A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.
Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.
The task is to determine minimal crossing time for the whole group.
Input
The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).
Output
The output contains one line with the result.
Sample Input
4 6 7 6 5
Sample Output
29
Source
Northeastern Europe 2001, Western Subregion
题目的意思是说,几个人过桥(有的题目是用船过河),因为桥很窄,每次只能有两个人通过,因为看不清,还要用一火把照明(总共只有一个火把),两个人同时过桥的时候,花费的时间为两个人中速度最慢的那个人花费的时间.现给出N个人的单独过桥时需花费的时间,求出这N个人全部过桥要花费多长时间...
/*最佳方案构造：以下是构造N个人(N≥1)过桥最佳方案的方法：
1) 如果N=1、2，所有人直接过桥。
2) 如果N=3，由最快的人往返一次把其他两人送过河。
3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；
而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。那么
当2b＞a+y时，使用模式一将Z和Y移动过桥；
当2b＜a+y时，使用模式二将Z和Y移动过桥；
当2b＝a+y时，使用模式一将Z和Y移动过桥。
这样就使问题转变为N-2个旅行者的情形，从而递归解决之。
……
A Z →
A ←
……
也就是“由A护送到对岸，A返回”，称作“模式一”。
……
……
第n-2步： A B →
第n-1步： A ←
第n步： Y Z →
第n+1步： B ←
……
这个模式是“由A和B护送到对岸，A和B返回”，称作“模式二”。
http://www.oursci.org/magazine/200204/020411-01.htm
2 import java.util.Iterator;
3 import java.util.Map;
4
5 public class BridgeAcross {
6
7 static Map humanInfo;
8
9 public BridgeAcross() {
10 Map<String, Integer> humanInfo = new HashMap<String, Integer>();
11 humanInfo.put("name1", 1);
12 humanInfo.put("name2", 2);
13 humanInfo.put("name3", 5);
14 humanInfo.put("name4", 7);
15 this.humanInfo = humanInfo;
16 }
17
18 public static Map getHumanInfo() {
19 return humanInfo;
20 }
21
22 public void setHumanInfo(Map humanInfo) {
23 this.humanInfo = humanInfo;
24 }
25
26 public static int minTime(int[] times) {
27 int[] time_sorted = sort(times);
28 return search(time_sorted);
29 }
30
31 public static int search(int[] times) {
32 int n = times.length;
33 if (n == 1)
34 return times[0];
35 else if (n == 2) {
36 System.out.println("-->" + getHuman(times[0]) + "+"
37 + getHuman(times[1]));
38 return times[1];
39 } else if (n == 3) {
40 System.out.println("-->" + getHuman(times[0]) + "+"
41 + getHuman(times[1]));
42 System.out.println("<--" + getHuman(times[0]));
43 System.out.println("-->" + getHuman(times[0]) + "+"
44 + getHuman(times[2]));
45 return (times[0] + times[1] + times[2]);
46 } else {
47 int[] time_temp = remainingTime(times);
48 if (2 * times[1] > times[0] + times[n - 2]) {
49 System.out.println("-->" + getHuman(times[0]) + "+"
50 + getHuman(times[1]));
51 System.out.println("<--" + getHuman(times[0]));
52 System.out.println("-->" + getHuman(times[0]) + "+"
53 + getHuman(times[n - 1]));
54 System.out.println("<--" + getHuman(times[0]));
55 System.out.println("-->" + getHuman(times[0]) + "+"
56 + getHuman(times[n - 2]));
57 System.out.println("<--" + getHuman(times[0]));
58 return 2 * times[0] + times[n - 1] + times[n - 2]
59 + search(time_temp);
60 } else {
61 System.out.println("-->" + getHuman(times[0]) + "+"
62 + getHuman(times[1]));
63 System.out.println("<--" + getHuman(times[0]));
64 System.out.println("-->" + getHuman(times[n - 1]) + "+"
65 + getHuman(times[n - 2]));
66 System.out.println("<--" + getHuman(times[1]));
67 // System.out.println("-->" + getHuman(times[0]) + "+" +
68 // getHuman(times[1]));
69 return 2 * times[1] + times[n - 1] + times[0]
70 + search(time_temp);
71 }
72 }
73 }
74
75 public static int[] sort(int[] times) {
76 int temp = 0;
77 for (int k = 0; k < times.length - 1; k++) {
78 for (int i = 0; i < times.length - 1; i++) {
79 if (times[i + 1] < times[i]) {
80 temp = times[i + 1];
81 times[i + 1] = times[i];
82 times[i] = temp;
83 }
84 }
85 }
86 return times;
87 }
88
89 public static int[] remainingTime(int[] times) {
90 int[] sub_time = new int[times.length - 2];
91 for (int i = 0; i < sub_time.length; i++) {
92 sub_time[i] = times[i];
93 }
94 return sub_time;
95 }
96
97 public static String getHuman(int time) {
98 Map map = getHumanInfo();
99 Iterator iterator = map.entrySet().iterator();
100 while (iterator.hasNext()) {
101 Map.Entry emtry = (Map.Entry) iterator.next();
102 int value = (Integer) emtry.getValue();
103 if (time == value) {
104 return (String) emtry.getKey();
105 }
106 }
107 return "";
108 }
109
110 public static int[] getTimes() {
111 int[] times = new int[getHumanInfo().size()];
112 int i = 0;
113 Iterator iterator = getHumanInfo().entrySet().iterator();
114 while (iterator.hasNext()) {
115 Map.Entry emtry = (Map.Entry) iterator.next();
116 times[i++] = (Integer) emtry.getValue();
117 }
118 return times;
119 }
120
121 /**
122 * @param args
123 */
124 public static void main(String[] args) {
125 BridgeAcross bridge = new BridgeAcross();
126 int[] times = bridge.getTimes();
127 System.out.println(minTime(times));
128 }
129
130 }
131