?

過河問題

時(shí)間限制：1000 ms ?|? 內(nèi)存限制：65535 KB 難度：5 描述

在漆黑的夜里，N位旅行者來到了一座狹窄而且沒有護(hù)欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個(gè)人一共只帶了一只手電筒，而橋窄得只夠讓兩個(gè)人同時(shí)過。如果各自單獨(dú)過橋的話，N人所需要的時(shí)間已知；而如果兩人同時(shí)過橋，所需要的時(shí)間就是走得比較慢的那個(gè)人單獨(dú)行動(dòng)時(shí)所需的時(shí)間。問題是，如何設(shè)計(jì)一個(gè)方案，讓這N人盡快過橋。?

輸入

第一行是一個(gè)整數(shù)T(1<=T<=20)表示測(cè)試數(shù)據(jù)的組數(shù)
每組測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)N(1<=N<=1000)表示共有N個(gè)人要過河
每組測(cè)試數(shù)據(jù)的第二行是N個(gè)整數(shù)Si,表示此人過河所需要花時(shí)間。(0<Si<=100)

輸出

輸出所有人都過河需要用的最少時(shí)間

樣例輸入

1 4 1 2 5 10

樣例輸出

17 View Code 1 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 int array[1002]; 7 int main() 8 { 9 int ncase,person,time,i; 10 scanf("%d",&ncase); 11 while(ncase--) 12 { 13 time=0; 14 scanf("%d",&person); 15 for(i=1;i<=person;i++) 16 scanf("%d",&array[i]); 17 sort(array,array+person+1); 18 while(person>3) 19 { 20 time+=min(array[1]+array[2]*2+array[person],array[1]*2+array[person-1]+array[person]); 21 person-=2; 22 } 23 time+=array[person]; 24 if(person==3)time+=array[1]+array[2]; 25 printf("%d\n",time); 26 } 27 return 0; 28 } 29 30 31 32 33 34 35 36

?

總結(jié)

以上是生活随笔為你收集整理的NYOJ47过河问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。