一個(gè)簡(jiǎn)單的智力問(wèn)題如下：有四個(gè)人要過(guò)一條河，河上一個(gè)橋，每次最多只允許兩個(gè)人過(guò)，且過(guò)河必須手電筒，只有一把手電筒，每個(gè)人完成過(guò)河的時(shí)間是不同的，兩個(gè)人過(guò)河的總時(shí)間為慢者單獨(dú)過(guò)河的時(shí)間。求四個(gè)人最終都過(guò)河需要的總時(shí)間。如，第一個(gè)人單獨(dú)過(guò)河需要1min，第二個(gè)人單獨(dú)過(guò)河需要2min，第三個(gè)人過(guò)河需要5min，第四個(gè)人過(guò)河需要10min，則總的過(guò)河時(shí)間為：1和2先過(guò)河，然后1把手電筒送回來(lái)，總共需要3min，然后3和4過(guò)河，2把手電筒送回來(lái)，需要10+2=12min，然后1和2再過(guò)河，總共需要3+12+2 = 17min。
這個(gè)問(wèn)題其實(shí)也可以采用圖論的方式來(lái)解決，這個(gè)方法很新穎，也很巧妙，具體請(qǐng)參考
http://blog.csdn.net/w468917145/article/details/4601882
這里想要講的是題目的要求不變，但是現(xiàn)在不僅僅四個(gè)人，而是有n個(gè)人，給定這n個(gè)人每個(gè)人單獨(dú)過(guò)橋的時(shí)間，求n個(gè)人最終均過(guò)河所需要的最短時(shí)間。
該怎么做呢？其實(shí)想想剛才的四個(gè)人的過(guò)程，1和2先過(guò)河的原因是希望能留下一個(gè)人，等最慢的和次慢的過(guò)河之后之前留下的這個(gè)人能夠把手電筒送回來(lái)。那么其實(shí)每次重復(fù)的過(guò)程就是最快的和次快的先過(guò)，然后最快的送手電筒回來(lái)，然后最慢的和次慢的再一起過(guò)河（這樣能夠讓本來(lái)都要耗費(fèi)很長(zhǎng)時(shí)間的兩個(gè)人一次性過(guò)河，從而節(jié)省時(shí)間），然后再讓次慢的回來(lái)送手電筒，這樣其實(shí)就將問(wèn)題規(guī)模從1~n=>1~n-2，而問(wèn)題狀態(tài)不變。從而可以重復(fù)上述過(guò)程直到只剩下3個(gè)人或者2個(gè)人。
上述的解法在每次運(yùn)送完當(dāng)前最慢和次慢的兩個(gè)人所耗費(fèi)的時(shí)間為time[n] + 2*time[2] + time[1]。但是有沒(méi)有想過(guò)根本不讓次快的參與運(yùn)送過(guò)程，每次都讓最快的運(yùn)送，這樣時(shí)間就是time[n] + time[n - 1] + 2*time[1]。因此，每次運(yùn)送最慢的和次慢的兩個(gè)人之前都要判斷到底是需要2參與運(yùn)送還是只需要1參與運(yùn)送就可了。
借用問(wèn)題
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 閱讀(2228)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
算法基礎(chǔ)