一個簡單的智力問題如下：有四個人要過一條河，河上一個橋，每次最多只允許兩個人過，且過河必須手電筒，只有一把手電筒，每個人完成過河的時間是不同的，兩個人過河的總時間為慢者單獨過河的時間。求四個人最終都過河需要的總時間。如，第一個人單獨過河需要1min，第二個人單獨過河需要2min，第三個人過河需要5min，第四個人過河需要10min，則總的過河時間為：1和2先過河，然后1把手電筒送回來，總共需要3min，然后3和4過河，2把手電筒送回來，需要10+2=12min，然后1和2再過河，總共需要3+12+2 = 17min。
這個問題其實也可以采用圖論的方式來解決，這個方法很新穎，也很巧妙，具體請參考
http://blog.csdn.net/w468917145/article/details/4601882
這里想要講的是題目的要求不變，但是現在不僅僅四個人，而是有n個人，給定這n個人每個人單獨過橋的時間，求n個人最終均過河所需要的最短時間。
該怎么做呢？其實想想剛才的四個人的過程，1和2先過河的原因是希望能留下一個人，等最慢的和次慢的過河之后之前留下的這個人能夠把手電筒送回來。那么其實每次重復的過程就是最快的和次快的先過，然后最快的送手電筒回來，然后最慢的和次慢的再一起過河（這樣能夠讓本來都要耗費很長時間的兩個人一次性過河，從而節省時間），然后再讓次慢的回來送手電筒，這樣其實就將問題規模從1~n=>1~n-2，而問題狀態不變。從而可以重復上述過程直到只剩下3個人或者2個人。
上述的解法在每次運送完當前最慢和次慢的兩個人所耗費的時間為time[n] + 2*time[2] + time[1]。但是有沒有想過根本不讓次快的參與運送過程，每次都讓最快的運送，這樣時間就是time[n] + time[n - 1] + 2*time[1]。因此，每次運送最慢的和次慢的兩個人之前都要判斷到底是需要2參與運送還是只需要1參與運送就可了。
借用問題
http://acm.nyist.net/JudgeOnline/problem.php?pid=47 程序代碼如下：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX 1005
5
6 int people[MAX];
7
8 int cmp(const void *a, const void *b) {
9 int *x = (int *)a;
10 int *y = (int *)b;
11 return *x > *y;
12 }
13
14 int main() {
15 int cases;
16 scanf("%d", &cases);
17 while (cases--) {
18 int n, i;
19 int res = 0;
20 scanf("%d", &n);
21 for (i = 0; i < n; ++i) {
22 scanf("%d", &people[i]);
23 }
24 qsort(people, n, sizeof(int), cmp);
25 if (n == 1) {
26 printf("%d\n", people[0]);
27 continue;
28 } else if (n == 2) {
29 printf("%d\n", people[1]);
30 continue;
31 } else {
32 int i = n - 1;
33 while (i > 2) {
34 int res1 = people[0] + (people[1] << 1) + people[i];
35 int res2 = people[i] + people[i - 1] + (people[0] << 1);
36 res = res1 > res2 ? res2 : res1;
37 i -= 2;
38 }
39 if (i == 2) {
40 res += people[0] + people[1] + people[2];
41 } else {
42 res += people[1];
43 }
44 }
45 printf("%d\n", res);
46 }
47 return 0;
48 }
呵呵
posted on 2012-09-17 18:56
myjfm 閱讀(2236)
評論(1) 編輯 收藏 引用 所屬分類:
算法基礎