The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

POJ 1700-過河問題經典智力題

題目描述：在漆黑的夜里，四位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，四個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過。如果各自單獨過橋的話，四人所需要的時間分別是1、2、5、8分鐘；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這四人盡快過橋。

解題思路：
當人數等于1，2，3的時候：答案很容易得出；
當人數大于等于4時：

若設過橋速度最快的那個人過橋時間為a,第二快為b;過橋第二慢的那個人過橋時間為y,最慢為z;
此時有兩種過橋方案：
一.最快和次快的人先過，然后最快的回來，然后最慢與次慢的人再過，次快的回來；
二.最快的和最慢的過，快的回來，在和次慢的過，快的再回來；

第一種方法時間為b*2+a+z
第二種方法時間為y+z+2*a
如果第一種大于第二種有2*b+a+z>y+z+2*a
化簡得
2*b>y+a;
此時只要比較2*b和a+y的大小即可知道那種方法更優 O(∩_∩)O~ 編程解決即可

#include<iostream>

#include<algorithm>

#include<numeric>

using namespace std;

int a[1000];

int main()

{

int testcase;

int n;

int i;

int j;

int sum=0;

scanf("%d",&testcase);

for(j=1;j<=testcase;j++)

{

sum=0;

scanf("%d",&n);

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

sort(a+1,a+1+n);

while(n)

{

if(n==1)

{

sum+=a[1];

n=0;

}

else if(n==2)

{

sum+=a[2];

n=0;

}

else if(n==3)

{

sum+=(a[2]+a[3]+a[1]);

n=0;

}

else if(n>=4)

{

if(2*a[2]>a[1]+a[n-1])

{

sum+=(a[n-1]+a[n])+2*a[1];

n-=2;

}

else

{

sum+=(a[2]+a[1]+a[n]+a[2]);

n-=2;

}

printf("%d\n",sum);

}

system("pause");

return 0;

}

說句題外話，據說去年南大保研的面試題就是這道題，一模一樣，呵呵只可惜我還沒到保研的時間。。。

posted on 2009-03-28 22:58 abilitytao 閱讀(3148) 評論(10) 編輯收藏引用

用第二種方法就是：
“二.最快的和最慢的過，快的回來，在和次慢的過，快的再回來；”
“第二種方法時間為y+z+2*a”
是怎么過去的呢？？？

az先過 a回來
ay過 a回來
ab過

時間是：z+a+y+a+b = z+y+2*a+b啊
怎么變成 z+y+2*a 了呢？

回復更多評論

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 15:32 菜鳥

就是好象最后b還沒有過去，就結束過河了…… 回復更多評論

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 16:42 菜鳥

知道了…………
還是謝謝你……

回復更多評論

# re: POJ 1700-過河問題經典智力題 2009-04-04 17:05 abilitytao

@菜鳥
你沒看懂我的意思其實以上的分析給出的是每一步的決策
是一個循環，你沒有注意到while(n)這個循環語句嗎？
當剩下的人數不斷變化的時候，我們要根據人數的情況做相應的決策。
并不是一次就全都過去了丫:-) 回復更多評論

# re: POJ 1700-過河問題經典智力題 2009-07-31 12:41 Linz

分析得很透徹。贊回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: POJ 1700-過河問題經典智力題 2009-03-29 01:03 陳梓瀚(vczh)

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 13:44 abilitytao

# re: POJ 1700-過河問題經典智力題 2009-03-29 14:58 funcoding

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 15:05 abilitytao

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 15:30 abilitytao

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 15:29 菜鳥

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 15:32 菜鳥

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 16:42 菜鳥

# re: POJ 1700-過河問題經典智力題 2009-04-04 17:05 abilitytao

# re: POJ 1700-過河問題經典智力題 2009-07-31 12:41 Linz

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1700-過河問題經典智力題

評論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1700-過河問題 經典智力題

評論

# re: POJ 1700-過河問題 經典智力題 2009-03-29 01:03 陳梓瀚(vczh)

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-03-29 13:44 abilitytao

# re: POJ 1700-過河問題 經典智力題 2009-03-29 14:58 funcoding

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-03-29 15:05 abilitytao

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-03-29 15:30 abilitytao

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-04-04 15:29 菜鳥

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-04-04 15:32 菜鳥

# re: POJ 1700-過河問題 經典智力題[未登錄] 2009-04-04 16:42 菜鳥

# re: POJ 1700-過河問題 經典智力題 2009-04-04 17:05 abilitytao

# re: POJ 1700-過河問題 經典智力題 2009-07-31 12:41 Linz

POJ 1700-過河問題經典智力題

# re: POJ 1700-過河問題經典智力題 2009-03-29 01:03 陳梓瀚(vczh)

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 13:44 abilitytao

# re: POJ 1700-過河問題經典智力題 2009-03-29 14:58 funcoding

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 15:05 abilitytao

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-03-29 15:30 abilitytao

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 15:29 菜鳥

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 15:32 菜鳥

# re: POJ 1700-過河問題經典智力題[未登錄] 2009-04-04 16:42 菜鳥

# re: POJ 1700-過河問題經典智力題 2009-04-04 17:05 abilitytao

# re: POJ 1700-過河問題經典智力題 2009-07-31 12:41 Linz